×

Length-bounded cuts: proper interval graphs and structural parameters. (English) Zbl 1505.68032

The paper studies a variant of the Edge Cut problem called the Length-Bounded Cut problem, which is the cut problem related to the variant of the Edge Disjoint Paths problem. The task of the Length-Bounded Cut problem is to find a set \(F\) of at most \(\beta\) edges such that each \(s\)-\(t\)-path of length at most \(\lambda\) in \(G\) contains some edge in \(F\), i.e., there is no \(s\)-\(t\)-path of length at most \(\lambda\) in \(G-F\).
The Length-Bounded Cut problem is polynomially solvable for \(\lambda=|V|\) as it reduces to Edge Cut and also for \(\lambda\le 3\), while it is NP-hard for the remaining values \(\lambda\ge 4\). This paper studies Length-Bounded Cut for special graph classes and confirms a conjecture of C. Bazgan et al. [Networks 73, No. 1, 23–37 (2019; Zbl 1407.90090)] that it can be solved in polynomial time on proper interval graphs. The authors give a dynamic-programming-based algorithm for the problem with running time \(O(n^2\cdot m)\).
Regarding parameterized complexity, the authors show that the Length-Bounded Cut problem is W[1]-hard for the feedback vertex number and for the combined parameter pathwidth and maximum degree of the input graph \(G\).
The above results imply that, assuming the Exponential Time Hypothesis, there is no \(f(k)\cdot n^{o(k)}\)-time algorithm for Length-Bounded Cut, where \(k\) is the pathwidth of the input graph.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68Q27 Parameterized complexity, tractability and kernelization

Citations:

Zbl 1407.90090
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bentert, M.; Heeger, K.; Knop, D., Length-bounded cuts: proper interval graphs and structural parameters, (31st International Symposium on Algorithms and Computation. 31st International Symposium on Algorithms and Computation, ISAAC 2020 (2020)), 36:1-36:14 · Zbl 07765394
[2] Ford, L. R.; Fulkerson, D. R., Maximal flow through a network, Can. J. Math., 8, 399-404 (1956) · Zbl 0073.40203
[3] Dinitz, Y., Dinitz’ algorithm: the original version and Even’s version, (Theoretical Computer Science, Essays in Memory of Shimon Even (2006)), 218-240
[4] Malhotra, V. M.; Kumar, M. P.; Maheshwari, S. N., An O(|V|^3) algorithm for finding maximum flows in networks, Inf. Process. Lett., 7, 6, 277-278 (1978) · Zbl 0391.90041
[5] Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency, Vol. 24 (2003), Springer Science & Business Media · Zbl 1041.90001
[6] Adámek, J.; Koubek, V., Remarks on flows in network with short paths, Comment. Math. Univ. Carol., 12, 661-667 (1971) · Zbl 0223.05108
[7] Mahjoub, A. R.; McCormick, S. T., Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation, Math. Program., 124, 1-2, 271-284 (2010) · Zbl 1198.90072
[8] Baier, G.; Erlebach, T.; Hall, A.; Köhler, E.; Kolman, P.; Pangrác, O.; Schilling, H.; Skutella, M., Length-bounded cuts and flows, ACM Trans. Algorithms, 7, 1, Article 4 pp. (2010) · Zbl 1295.68119
[9] Kolman, P.; Scheideler, C., Improved bounds for the unsplittable flow problem, J. Algorithms, 61, 1, 20-44 (2006) · Zbl 1101.68110
[10] Huygens, D.; Labbé, M.; Mahjoub, A. R.; Pesneau, P., The two-edge connected hop-constrained network design problem: valid inequalities and branch-and-cut, Networks, 49, 1, 116-133 (2007) · Zbl 1131.90065
[11] Huygens, D.; Ridha Mahjoub, A., Integer programming formulations for the two 4-hop-constrained paths problem, Networks, 49, 2, 135-144 (2007) · Zbl 1180.90200
[12] Gouveia, L.; Patrício, P.; de Sousa, A., Hop-constrained node survivable network design: an application to mpls over wdm, Netw. Spat. Econ., 8, 1, 3-21 (2008) · Zbl 1172.90339
[13] Golovach, P. A.; Thilikos, D. M., Paths of bounded length and their cuts: parameterized complexity and algorithms, Discrete Optim., 8, 1, 72-86 (2011) · Zbl 1248.90071
[14] Fluschnik, T.; Hermelin, D.; Nichterlein, A.; Niedermeier, R., Fractals for kernelization lower bounds, SIAM J. Discrete Math., 32, 1, 656-681 (2018) · Zbl 1388.68112
[15] Dvořák, P.; Knop, D., Parameterized complexity of length-bounded cuts and multicuts, Algorithmica, 80, 12, 3597-3617 (2018) · Zbl 1400.90258
[16] Gutin, G. Z.; Jones, M.; Wahlström, M., The mixed Chinese postman problem parameterized by pathwidth and treedepth, SIAM J. Discrete Math., 30, 4, 2177-2205 (2016) · Zbl 1351.05100
[17] Kellerhals, L.; Koana, T., Parameterized complexity of geodetic set, (15th International Symposium on Parameterized and Exact Computation. 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 (2020)), 20:1-20:14 · Zbl 07764111
[18] Knop, D.; Schierreich, S.; Suchý, O., Balancing the spread of two opinions in sparse social networks (2021), CoRR
[19] Kolman, P., On algorithms employing treewidth for l-bounded cut problems, J. Graph Algorithms Appl., 22, 2, 177-191 (2018) · Zbl 1384.05147
[20] Bazgan, C.; Fluschnik, T.; Nichterlein, A.; Niedermeier, R.; Stahlberg, M., A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths, Networks, 73, 1, 23-37 (2019) · Zbl 1407.90090
[21] Stahlberg, M., Finding the most vital edges for shortest paths (2016), Technische Universität Berlin, Bachelor thesis
[22] Le Brandstädt Van Bang, A.; Spinrad, J. P., Graph Classes: A Survey (1999), Society for Industrial and Applied Mathematics · Zbl 0919.05001
[23] Impagliazzo, R.; Paturi, R., On the complexity of k-sat, J. Comput. Syst. Sci., 62, 2, 367-375 (2001) · Zbl 0990.68079
[24] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052
[25] Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001
[26] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness II: on completeness for W[1], Theor. Comput. Sci., 141, 1&2, 109-131 (1995) · Zbl 0873.68059
[27] Pietrzak, K., On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems, J. Comput. Syst. Sci., 67, 4, 757-771 (2003) · Zbl 1092.68049
[28] Fellows, M. R.; Hermelin, D.; Rosamond, F. A.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theor. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.