Fractals for kernelization lower bounds. (English) Zbl 1388.68112
Summary: The composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. In particular, answering an open question of P. A. Golovach and D. M. Thilikos [Discrete Optim. 8, No. 1, 72–86 (2011; Zbl 1248.90071)], we show that, unless \(\mathrm{NP}\subseteq {\mathrm{coNP}}/{\mathrm{poly}}\), the NP-hard Length-Bounded Edge-Cut (LBEC) problem (delete at most \(k\) edges such that the resulting graph has no \(s\)-\(t\) path of length shorter than \(\ell\)) parameterized by the combination of \(k\) and \(\ell\) has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex-deletion problems. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
parameterized complexity; polynomial-time data reduction; lower bounds; cross-compositions; graph modification problems; interdiction problemsCitations:
Zbl 1248.90071References:
| [1] | G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, {\it Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties}, Springer, New York, 1999. · Zbl 0937.68002 |
| [2] | G. Baier, T. Erlebach, A. Hall, E. Köhler, P. Kolman, O. Pangrác, H. Schilling, and M. Skutella, {\it Length-bounded cuts and flows}, ACM Trans. Algorithms, 7 (2010), 4, . · Zbl 1295.68119 |
| [3] | C. Bazgan, M. Chopin, M. Cygan, M. R. Fellows, F. V. Fomin, and E. J. van Leeuwen, {\it Parameterized complexity of firefighting}, J. Comput. System Sci., 80 (2014), pp. 1285-1297, . · Zbl 1411.68046 |
| [4] | C. Bazgan, A. Nichterlein, and R. Niedermeier, {\it A refined complexity analysis of finding the most vital edges for undirected shortest paths}, in Proceedings of the 9th International Conference on Algorithms and Complexity, Lecture Notes in Comput. Sci. 9079, Springer, New York, 2015, pp. 47-60, . · Zbl 1459.68152 |
| [5] | M. A. Bekos, M. Gronemann, and C. N. Raftopoulou, {\it Two-page book embeddings of 4-planar graphs}, in Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, LIPIcs Leibniz Int. Proc. Inform. 25, Schloss Dagstuhl Leibniz-Zentrum für Informatik, Wadern, 2014, pp. 137-148. · Zbl 1359.05026 |
| [6] | R. Bevern, R. Bredereck, M. Chopin, S. Hartung, F. Hüffner, A. Nichterlein, and O. Suchý, {\it Fixed-parameter algorithms for DAG partitioning}, Discrete Appl. Math., 220 (2017), pp. 134-160. · Zbl 1355.05204 |
| [7] | H. L. Bodlaender, {\it A partial \(k\)-arboretum of graphs with bounded treewidth}, Theoret. Comput. Sci., 209 (1998), pp. 1-45, . · Zbl 0912.68148 |
| [8] | H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, {\it On problems without polynomial kernels}, J. Comput. System Sci., 75 (2009), pp. 423-434, . · Zbl 1192.68288 |
| [9] | H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos, {\it (Meta) Kernelization}, J. ACM, 63 (2016), pp. 44:1-44:69, . · Zbl 1292.68089 |
| [10] | H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, {\it Kernelization lower bounds by cross-composition}, SIAM J. Discrete Math., 28 (2014), pp. 277-305, . · Zbl 1295.05222 |
| [11] | H. L. Bodlaender, S. Thomassé, and A. Yeo, {\it Kernel bounds for disjoint cycles and disjoint paths}, Theoret. Comput. Sci., 412 (2011), pp. 4570-4578, . · Zbl 1221.68099 |
| [12] | L. Cai, J. Chen, R. G. Downey, and M. R. Fellows, {\it Advice classes of parameterized tractability}, Ann. Pure Appl. Logic, 84 (1997), pp. 119-138, . · Zbl 0873.68071 |
| [13] | J. Chen, H. Fernau, I. A. Kanj, and G. Xia, {\it Parametric duality and kernelization: Lower bounds and upper bounds on kernel size}, SIAM J. Comput., 37 (2007), pp. 1077-1106, . · Zbl 1141.05075 |
| [14] | M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, {\it Parameterized Algorithms}, Springer, New York, 2015. · Zbl 1334.90001 |
| [15] | M. Cygan, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and M. Wahlström, {\it Clique cover and graph separation: New incompressibility results}, ACM Trans. Comput. Theory, 6 (2014), 6, . · Zbl 1321.68302 |
| [16] | H. Dell and D. van Melkebeek, {\it Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses}, J. ACM, 61 (2014), pp. 23:1-23:27, . · Zbl 1321.68274 |
| [17] | R. Diestel, {\it Graph Theory}, 4th ed., Grad. Texts in Math. 173, Springer, New York, 2010. · Zbl 1204.05001 |
| [18] | M. Dom, D. Lokshtanov, and S. Saurabh, {\it Kernelization lower bounds through colors and IDs}, ACM Trans. Algorithms, 11 (2014), 13, . · Zbl 1248.68243 |
| [19] | R. G. Downey and M. R. Fellows, {\it Fundamentals of Parameterized Complexity}, Texts in Comput. Sci., Springer, New York, 2013. · Zbl 1358.68006 |
| [20] | A. Drucker, {\it New limits to classical and quantum instance compression}, SIAM J. Comput., 44 (2015), pp. 1443-1479, . · Zbl 1330.68092 |
| [21] | P. Dvořák and D. Knop, {\it Parametrized complexity of length-bounded cuts and multi-cuts}, in Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci. 9076, Springer, New York, 2015, pp. 441-452, . · Zbl 1454.68056 |
| [22] | M. R. Fellows, A. Kulik, F. A. Rosamond, and H. Shachnai, {\it Parameterized approximation via fidelity preserving transformations}, in Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Comput. Sci. 7391, Springer, New York, 2012, pp. 351-362, . · Zbl 1272.68459 |
| [23] | J. Flum and M. Grohe, {\it Parameterized Complexity Theory}, Springer, New York, 2006. · Zbl 1143.68016 |
| [24] | T. Fluschnik, S. Kratsch, R. Niedermeier, and M. Sorge, {\it The parameterized complexity of the minimum shared edges problem}, in Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, LIPIcs Leibniz Int. Proc. Inform. 45, Schloss Dagstuhl Leibniz-Zentrum fuer Informatik, 2015, pp. 448-462, . · Zbl 1366.68090 |
| [25] | L. Fortnow and R. Santhanam, {\it Infeasibility of instance compression and succinct PCPs for NP}, J. Comput. System Sci., 77 (2011), pp. 91-106, . · Zbl 1233.68144 |
| [26] | M. R. Garey, D. S. Johnson, and L. J. Stockmeyer, {\it Some simplified NP-complete graph problems}, Theoret. Comput. Sci., 1 (1976), pp. 237-267, . · Zbl 0338.05120 |
| [27] | P. A. Golovach and D. M. Thilikos, {\it Paths of bounded length and their cuts: Parameterized complexity and algorithms}, Discrete Optim., 8 (2011), pp. 72-86, . · Zbl 1248.90071 |
| [28] | S. Guillemot, F. Havet, C. Paul, and A. Perez, {\it On the (non-)existence of polynomial kernels for \(P_l\)-free edge modification problems}, Algorithmica, 65 (2013), pp. 900-926, . · Zbl 1262.68048 |
| [29] | J. Guo and R. Niedermeier, {\it Invitation to data reduction and problem kernelization}, ACM SIGACT News, 38 (2007), pp. 31-45, . |
| [30] | V. Guruswami and E. Lee, {\it Inapproximability of feedback vertex set for bounded length cycles}, Electron. Colloq. Comput. Complexity, 21 (2014), 6, . |
| [31] | L. S. Heath, {\it Algorithms for Embedding Graphs in Books}, Ph.D. thesis, University of North Carolina at Chapel Hill, 1985. |
| [32] | A. Itai, Y. Perl, and Y. Shiloach, {\it The complexity of finding maximum disjoint paths with length constraints}, Networks, 12 (1982), pp. 277-286, . · Zbl 0504.68041 |
| [33] | S. Kratsch, {\it Recent developments in kernelization: A survey}, Bull. EATCS, 113 (2014), pp. 58-97, . · Zbl 1409.68144 |
| [34] | D. Lokshtanov, D. Marx, and S. Saurabh, {\it Lower bounds based on the exponential time hypothesis}, Bull. EATCS, 105 (2011), pp. 41-72, . · Zbl 1258.68068 |
| [35] | D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh, {\it Lossy kernelization}, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 224-237, . · Zbl 1370.68136 |
| [36] | K. Malik, A. K. Mittal, and S. K. Gupta, {\it The \(k\) most vital arcs in the shortest path problem}, Oper. Res. Lett., 8 (1989), pp. 223-227, . · Zbl 0669.90090 |
| [37] | D. Marx, {\it Parameterized complexity and approximation algorithms}, Computer J. 51 (2008), pp. 60-78, . |
| [38] | K. Menger, {\it Über reguläre Baumkurven}, Math. Ann., 96 (1927), pp. 572-582. · JFM 52.0598.02 |
| [39] | B. Mohar, {\it Face covers and the genus problem for apex graphs}, J. Combin. Theory Ser. B, 82 (2001), pp. 102-117, . · Zbl 1025.05019 |
| [40] | R. Niedermeier, {\it Invitation to Fixed-Parameter Algorithms}, Oxford University Press, New York, 2006. · Zbl 1095.68038 |
| [41] | F. Pan and A. Schild, {\it Interdiction problems on planar graphs}, Discrete Appl. Math., 198 (2016), pp. 215-231, . · Zbl 1327.05234 |
| [42] | B. Schieber, A. Bar-Noy, and S. Khuller, {\it The Complexity of Finding Most Vital Arcs and Nodes}, Tech. report, University of Maryland, College Park, 1995. |
| [43] | A. A. Schoone, H. L. Bodlaender, and J. van Leeuwen, {\it Diameter increase caused by edge deletion}, J. Graph Theory, 11 (1987), pp. 409-427, . · Zbl 0646.05038 |
| [44] | V. V. Vazirani, {\it Approximation Algorithms}, Springer, New York, 2001. · Zbl 0999.68546 |
| [45] | D. B. West, {\it Introduction to Graph Theory}, 2 ed., Prentice-Hall, Englewood Cliffs, NJ, 2000. |
| [46] | D. P. Williamson and D. B. Shmoys, {\it The Design of Approximation Algorithms}, Cambridge University Press, New York, 2011. · Zbl 1219.90004 |
| [47] | G. Xia and Y. Zhang, {\it On the small cycle transversal of planar graphs}, Theoret. Comput. Sci., 412 (2011), pp. 3501-3509, . · Zbl 1217.68114 |
| [48] | G. Xia and Y. Zhang, {\it Kernelization for cycle transversal problems}, Discrete Appl. Math., 160 (2012), pp. 1224-1231, . · Zbl 1242.05142 |
| [49] | M. Yannakakis, {\it Node- and edge-deletion NP-complete problems}, in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ACM, 1978, pp. 253-264, . · Zbl 1282.68131 |
| [50] | P. Zschoche, {\it On Finding Separators in Temporal Graphs}, Master’s thesis, Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, 2017; available online from . |
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.
