×

Parameterized complexity of length-bounded cuts and multicuts. (English) Zbl 1400.90258

Summary: We study the minimum length-bounded cut problem where the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least \(L + 1\) long. We show the problem can be computed in \(\mathsf{FPT}\) time with respect to \(L\) and the tree-width of the input graph \(G\) as parameters and with linear dependence of \(|V(G)|\) (i.e., in time \(f(L, \operatorname{tw}(G))|V(G)|\) for a computable function \(f\)). We derive an \(\mathsf{FPT}\) algorithm for a more general multi-commodity length-bounded cut problem when additionally parameterized by the number of terminals. For the former problem we show a \(\mathsf{W}[1]\)-hardness result when the parameterization is done by the path-width only (instead of the tree-width) and that this problem does not admit polynomial kernel when parameterized by path-width and \(L\). We also derive an \(\mathsf{FPT}\) algorithm for the minimum length-bounded cut problem when parameterized by the tree-depth, thus showing an interesting behavior for this problem and parameters tree-depth and path-width.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
05C12 Distance in graphs

Software:

Algorithm 97

References:

[1] Adámek, J.; Koubek, V., Remarks on flows in network with short paths, Comment. Math. Univ. Carol., 12, 661-667, (1971) · Zbl 0223.05108
[2] 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, 4:1-4:27, (2010) · Zbl 1295.68119 · doi:10.1145/1868237.1868241
[3] Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny, On problems without polynomial kernels, Journal of Computer and System Sciences, 75, 423-434, (2009) · Zbl 1192.68288 · doi:10.1016/j.jcss.2009.04.001
[4] COURCELLE, Bruno, Graph Rewriting: An Algebraic and Logic Approach, 193-242, (1990) · Zbl 0900.68282
[5] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https://doi.org/10.1007/978-3-319-21275-3 · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3
[6] Dahl, Geir; Gouveia, Luis, On the directed hop-constrained shortest path problem, Operations Research Letters, 32, 15-22, (2004) · Zbl 1056.90116 · doi:10.1016/S0167-6377(03)00026-9
[7] Dom, M.; Lokshtanov, D.; Saurabh, S.; Villanger, Y.; Grohe, M. (ed.); Niedermeier, R. (ed.), Capacitated domination and covering: a parameterized perspective, No. 5018, 78-90, (2008), Berlin · Zbl 1142.68371 · doi:10.1007/978-3-540-79723-4_9
[8] Dvořák, Pavel; Knop, Dušan, Parametrized Complexity of Length-Bounded Cuts and Multi-cuts, 441-452, (2015), Cham · Zbl 1454.68056
[9] Floyd, RW, Algorithm 97: shortest path, Commun. ACM, 5, 345, (1962) · doi:10.1145/367766.368168
[10] Fluschnik, T., Hermelin, D., Nichterlein, A., Niedermeier, R.: Fractals for kernelization lower bounds, with an application to length-bounded cut problems. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 25:1-25:14 (2016). https://doi.org/10.4230/LIPIcs.ICALP.2016.25 · Zbl 1388.68111
[11] Ford, LR; Fulkerson, DR, Maximal flow through a network, Can. J. Math., 8, 399-404, (1956) · Zbl 0073.40203 · doi:10.4153/CJM-1956-045-5
[12] Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Shrobe, H.E., Dietterich, T.G., Swartout, W.R. (eds.) Proceedings of the 8th National Conference on Artificial Intelligence, Boston, Massachusetts, July 29-August 3, 1990, vol. 2, pp. 4-9. AAAI Press/The MIT Press (1990). http://www.aaai.org/Library/AAAI/1990/aaai90-001.php
[13] Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pp. 710-716 (2016). http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12432 · Zbl 1451.90099
[14] Golovach, Petr A.; Thilikos, Dimitrios M., Paths of bounded length and their cuts: Parameterized complexity and algorithms, Discrete Optimization, 8, 72-86, (2011) · Zbl 1248.90071 · doi:10.1016/j.disopt.2010.09.009
[15] Gutin, Gregory; Jones, Mark; Wahlström, Magnus, Structural Parameterizations of the Mixed Chinese Postman Problem, 668-679, (2015), Berlin, Heidelberg · Zbl 1467.68074 · doi:10.1007/978-3-662-48350-3_56
[16] Huygens, D.; Labbé, M.; Mahjoub, AR; Pesneau, P., The two-edge connected hop-constrained network design problem: valid inequalities and branch-and-cut, Networks, 49, 116-133, (2007) · Zbl 1131.90065 · doi:10.1002/net.20146
[17] Itai, A.; Perl, Y.; Shiloach, Y., The complexity of finding maximum disjoint paths with length constraints, Networks, 12, 277-286, (1982) · Zbl 0504.68041 · doi:10.1002/net.3230120306
[18] Kloks, T.: Treewidth, Computations and Approximations. Lecture notes in computer science, vol. 842. Springer, New York, Inc (1994) · Zbl 0825.68144
[19] Kolman, P.: On algorithms for \(l\)-bounded cut problem. CoRR abs/1705.02390 (2017). arXiv:1705.02390
[20] Nešetřil, Jaroslav; Ossona de Mendez, Patrice, Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, 27, 1022-1041, (2006) · Zbl 1089.05025 · doi:10.1016/j.ejc.2005.01.010
[21] Nešetřil, J., de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics. Springer, Berlin (2012). https://books.google.cz/books?id=n8UuUePJ_iIC · Zbl 1268.05002 · doi:10.1007/978-3-642-27875-4
[22] Orlin, J.B.: Max flows in o(nm) time, or better. In: Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pp. 765-774 (2013). https://doi.org/10.1145/2488608.2488705 · Zbl 1293.05151
[23] Warshall, S., A theorem on Boolean matrices, J. ACM, 9, 11-12, (1962) · Zbl 0118.33104 · doi:10.1145/321105.321107
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.