Paths of bounded length and their cuts: parameterized complexity and algorithms. (English) Zbl 1248.90071
Summary: We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger’s theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length \(l\) of paths, the number \(k\) of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both \(k\) and \(l\) and hardness results when the parameter is only one of \(k\) and \(l\). Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C60 | Abstract computational complexity for mathematical programming problems |
Keywords:
bounded length disjoint paths; bounded length cuts; parameterized complexity; parameterized algorithmsReferences:
| [1] | Menger, K., Über reguläre Baumkurven, Math. Ann., 96, 572-582 (1927) · JFM 52.0598.02 |
| [2] | Dantzig, G. B.; Fulkerson, D. R., On the max-flow min-cut theorem of networks, (Linear Inequalities and Related Systems. Linear Inequalities and Related Systems, Annals of Mathematics Studies, vol. 38 (1956), Princeton University Press: Princeton University Press Princeton, NJ), 215-221 · Zbl 0072.37802 |
| [3] | Ford, L. R.; Fulkerson, D. R., Maximal flow through a network, Canad. J. Math., 8, 399-404 (1956) · Zbl 0073.40203 |
| [4] | Adámek, J.; Koubek, V., Remarks on flows in network with short paths, Comment. Math. Univ. Carolin., 12, 4, 661-667 (1971) · Zbl 0223.05108 |
| [5] | Lovász, L.; Neumann Lara, V.; Plummer, M., Mengerian theorems for paths of bounded length, Period. Math. Hungar., 9, 269-276 (1978) · Zbl 0393.05033 |
| [6] | Exoo, G., On line disjoint paths of bounded length, Discrete Math., 44, 317-318 (1983) · Zbl 0507.05041 |
| [7] | Niepel, L.; Šafaříková, D., On a generalization of Menger’s theorem, Acta Math. Univ. Comenian., 42-43, 275-284 (1983) · Zbl 0533.05037 |
| [8] | Itai, A.; Perl, Y.; Shiloach, Y., The complexity of finding maximum disjoint paths with length constraints, Networks, 12, 277-286 (1982) · Zbl 0504.68041 |
| [9] | Baier, G.; Erlebach, T.; Hall, A.; Köhler, E.; Schilling, H.; Skutella, M., Length-bounded cuts and flows, (Automata, Languages and Programming. Part I. Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci., vol. 4051 (2006), Springer: Springer Berlin), 679-690 · Zbl 1223.05294 |
| [10] | G. Baier, T. Erlebach, A. Hall, E. Köhler, P. Kolman, O. Pangrác, H. Schilling, M. Skutella, Length-bounded cuts and flows, ACM Trans. Algorithms (in press).; G. Baier, T. Erlebach, A. Hall, E. Köhler, P. Kolman, O. Pangrác, H. Schilling, M. Skutella, Length-bounded cuts and flows, ACM Trans. Algorithms (in press). · Zbl 1295.68119 |
| [11] | Bley, A., On the complexity of vertex-disjoint length-restricted path problems, Comput. Complexity, 12, 131-149 (2003) · Zbl 1085.68066 |
| [12] | Guruswami, V.; Khanna, S.; Rajaraman, R.; Shepherd, B.; Yannakakis, M., Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, J. Comput. System Sci., 67, 473-496 (2003) · Zbl 1114.68430 |
| [13] | Fleischer, L.; Skutella, M., The quickest multicommodity flow problem, (Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci., vol. 2337 (2002), Springer: Springer Berlin), 36-53 · Zbl 1049.90106 |
| [14] | Kolman, P.; Scheideler, C., Improved bounds for the unsplittable flow problem, (Proceedings of the Symposium on Discrete Algorithms (2002), ACM), 184-193 · Zbl 1241.68132 |
| [15] | Kolman, P.; Scheideler, C., Improved bounds for the unsplittable flow problem, J. Algorithms, 61, 1, 20-44 (2006) · Zbl 1101.68110 |
| [16] | Ronen, D.; Perl, Y., Heuristics for finding a maximum number of disjoint bounded paths, Networks, 14, 531-544 (1984) · Zbl 0575.90083 |
| [17] | Wagner, D.; Weihe, K., A linear-time algorithm for edge-disjoint paths in planar graphs, Combinatorica, 15, 135-150 (1995) · Zbl 0841.05086 |
| [18] | Hsu, D., On container width and length in graphs, groups, and networks, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 77, 4, 668-680 (1994), Dedicated to Professor Paul Erdős on the occasion of his 80th birthday (Special Section on Discrete Mathematics and its Applications) |
| [19] | Karp, R. M., On the computational complexity of combinatorial problems, Networks, 5, 1, 45-68 (1975), (Proceedings of the Symposium on Large-Scale Networks, Evanston, IL, USA, 18-19 April 1974) · Zbl 0324.05003 |
| [20] | Robertson, N.; Seymour, P. D., Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63, 65-110 (1995) · Zbl 0823.05038 |
| [21] | Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121 (1980) · Zbl 0419.05028 |
| [22] | Downey, R. G.; Fellows, M. R., (Parameterized Complexity. Parameterized Complexity, Monographs in Computer Science (1999), Springer-Verlag: Springer-Verlag New York) |
| [23] | Flum, J.; Grohe, M., (Parameterized Complexity Theory. Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series (2006), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1087.68034 |
| [24] | Niedermeier, R., (Invitation to Fixed-Parameter Algorithms. Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications, vol. 31 (2006), Oxford University Press: Oxford University Press Oxford) · Zbl 1095.68038 |
| [25] | Li, C.-L.; McCormick, T.; Simchi-Levi, D., The complexity of finding two disjoint paths with min-max objective function, Discrete Appl. Math., 26, 105-115 (1990) · Zbl 0693.05035 |
| [26] | Tragoudas, S.; Varol, Y. L., Computing disjoint paths with length constraints, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Cadenabbia, 1996. Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Cadenabbia, 1996, Lecture Notes in Comput. Sci., vol. 1197 (1997), Springer: Springer Berlin), 375-389 · Zbl 1539.68238 |
| [27] | Alon, N.; Yuster, R.; Zwick, U., Color-coding, J. Assoc. Comput. Mach., 42, 844-856 (1995) · Zbl 0885.68116 |
| [28] | Fellows, M.; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theoret. Comput. Sci., 410, 53-61 (2009) · Zbl 1161.68038 |
| [29] | Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308-340 (1991) · Zbl 0734.68073 |
| [30] | Borie, R. B., Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Algorithmica, 14, 123-137 (1995) · Zbl 0833.68089 |
| [31] | Kratochvíl, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Appl. Math., 52, 233-252 (1994) · Zbl 0810.68083 |
| [32] | Dom, M.; Lokshtanov, D.; Saurabh, S.; Villanger, Y., Capacitated domination and covering: a parameterized perspective, (IWPEC’08. IWPEC’08, LNCS, vol. 5018 (2008), Springer), 78-90 · Zbl 1142.68371 |
| [33] | Bodlaender, H.; Lokshtanov, D.; Penninkx, E., Planar capacitated dominating set is \(W [1]\)-hard, (IWPEC’09. IWPEC’09, LNCS, vol. 5917 (2009), Springer), 50-60 · Zbl 1273.68145 |
| [34] | Fomin, F. V.; Golovach, P. A.; Lokshtanov, D.; Saurabh, S., Algorithmic lower bounds for problems parameterized with clique-width, (SODA’10 (2010), ACM-SIAM), 493-502 · Zbl 1288.05269 |
| [35] | Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Hermelin, D., On problems without polynomial kernels, J. Comput. System Sci., 75, 8, 423-434 (2008) · Zbl 1192.68288 |
| [36] | Golovach, P. A.; Thilikos, D. M., Paths of bounded length and their cuts: parameterized complexity and algorithms, (IWPEC’09. IWPEC’09, LNCS, vol. 5917 (2009), Springer), 210-221 · Zbl 1273.68172 |
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.
