Document Open Access Logo

Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems

Authors Till Fluschnik, Danny Hermelin, André Nichterlein, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.25.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Till Fluschnik
Danny Hermelin
André Nichterlein
Rolf Niedermeier

Cite As Get BibTex

Till Fluschnik, Danny Hermelin, André Nichterlein, and Rolf Niedermeier. Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.25

Abstract

Bodlaender et al.'s [Bodlaender/Jansen/Kratsch,2014] cross-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 cross-compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. Roughly speaking, our new technique combines the advantages of serial and parallel composition. In particular, answering an open question of Golovach and Thilikos [Golovach/Thilikos,2011], we show that, unless NP subseteq coNP/poly, the NP-hard Length-Bounded Edge-Cut problem (delete at most k edges such that the resulting graph has no s-t path of length shorter than l) parameterized by the combination of k and l 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.

Subject Classification

Keywords
  • Parameterized complexity
  • polynomial-time data reduction
  • cross-compositions
  • lower bounds
  • graph modification problems
  • interdiction problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrác, Heiko Schilling, and Martin Skutella. Length-bounded cuts and flows. ACM Transactions on Algorithms, 7(1):4, 2010. URL: http://dx.doi.org/10.1145/1868237.1868241.
  2. Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, and Erik Jan van Leeuwen. Parameterized complexity of firefighting. Journal of Computer and System Sciences, 80(7):1285-1297, 2014. Google Scholar
  3. Cristina Bazgan, André Nichterlein, and Rolf Niedermeier. A refined complexity analysis of finding the most vital edges for undirected shortest paths. In Proc. of the 9th International Conference on Algorithms and Complexity (CIAC 2015), volume 9079 of LNCS, pages 47-60. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-18173-8_3.
  4. René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, and Ondřej Suchý. Parameterized complexity of dag partitioning. In Proc. of the 8th International Conference on Algorithms and Complexity (CIAC'13), volume 7878 of LNCS, pages 49-60. Springer, 2013. Google Scholar
  5. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423-434, 2009. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  6. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. URL: http://dx.doi.org/10.1137/120880240.
  7. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science, 412(35):4570-4578, 2011. Google Scholar
  8. Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows. Advice classes of parameterized tractability. Annals of Pure and Applied Logic, 84(1):119-138, 1997. Google Scholar
  9. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 4th edition, 2010. Google Scholar
  10. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and ids. ACM Transactions on Algorithms, 11(2):13, 2014. URL: http://dx.doi.org/10.1145/2650261.
  11. Pavel Dvořák and Dušan Knop. Parametrized complexity of length-bounded cuts and multi-cuts. In Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC 2015), volume 9076 of LNCS, pages 441-452. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-17142-5_37.
  12. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1):91-106, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.007.
  13. Petr A. Golovach and Dimitrios M. Thilikos. Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optimization, 8(1):72-86, 2011. URL: http://dx.doi.org/10.1016/j.disopt.2010.09.009.
  14. Jiong Guo and Rolf Niedermeier. Invitation to data reduction and problem kernelization. ACM SIGACT News, 38(1):31-45, 2007. Google Scholar
  15. Venkatesan Guruswami and Euiwoong Lee. Inapproximability of feedback vertex set for bounded length cycles. Electronic Colloquium on Computational Complexity (ECCC), 21:6, 2014. Google Scholar
  16. Alon Itai, Yehoshua Perl, and Yossi Shiloach. The complexity of finding maximum disjoint paths with length constraints. Networks, 12(3):277-286, 1982. URL: http://dx.doi.org/10.1002/net.3230120306.
  17. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113:58-97, 2014. Google Scholar
  18. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41-72, 2011. Google Scholar
  19. Kavindra Malik, Ashok K. Mittal, and Santosh K. Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4):223-227, 1989. Google Scholar
  20. Dániel Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  21. Karl Menger. Über reguläre Baumkurven. Mathematische Annalen, 96(1):572-582, 1927. Google Scholar
  22. Feng Pan and Aaron Schild. Interdiction problems on planar graphs. Discrete Applied Mathematics, 198:215-231, 2016. Google Scholar
  23. Anneke A. Schoone, Hans L. Bodlaender, and Jan van Leeuwen. Diameter increase caused by edge deletion. Journal of Graph Theory, 11(3):409-427, 1987. URL: http://dx.doi.org/10.1002/jgt.3190110315.
  24. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Google Scholar
  25. Ge Xia and Yong Zhang. On the small cycle transversal of planar graphs. Theoretical Computer Science, 412(29):3501-3509, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact