Document Open Access Logo

Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations

Authors Bart M. P. Jansen , Astrid Pieterse

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.48.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Bart M. P. Jansen
  • Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
Astrid Pieterse
  • Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

Funding

This work was supported by NWO Veni grant "Frontiers in Parameterized Preprocessing" and NWO Gravitation grant "Networks".

Cite As Get BibTex

Bart M. P. Jansen and Astrid Pieterse. Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.48

Abstract

We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of graphs F, the F-Deletion problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when F contains a planar graph, an instance (G,k) can be reduced in polynomial time to an equivalent one of size k^{O(1)}. In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the F-Deletion problem by the size of a vertex modulator whose removal results in a graph of constant treedepth eta.
We prove that for each set F of connected graphs and constant eta, the F-Deletion problem parameterized by the size of a treedepth-eta modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-Deletion. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of G-X. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal F-Deletion solution from a single connected component of G-X. By bounding the number of different types of behavior that can occur by a polynomial in |X|, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of F-Deletion such as Vertex Cover and Feedback Vertex Set. It also generalizes earlier preprocessing results for F-Deletion parameterized by a vertex cover, which is a treedepth-one modulator.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Kernelization
  • F-minor free deletion
  • Treedepth modulator
  • Structural parameterization

Metrics

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

Related Versions

References

  1. Hans L. Bodlaender. Kernelization: New upper and lower bound techniques. In Proc. 4th IWPEC, pages 17-37, 2009. URL: http://dx.doi.org/10.1007/978-3-642-11269-0_2.
  2. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  3. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. J. ACM, 63(5):44:1-44:69, 2016. URL: http://dx.doi.org/10.1145/2973749.
  4. Marin Bougeret and Ignasi Sau. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? CoRR, abs/1609.08095, 2016. URL: http://arxiv.org/abs/1609.08095.
  5. Marin Bougeret and Ignasi Sau. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? In Proc. 12th IPEC (2017), volume 89, pages 10:1-10:13, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.10.
  6. Hubie Chen and Moritz Müller. One hierarchy spawns another: Graph deconstructions and the complexity classification of conjunctive queries. In Proc. CSL-LICS 2014, pages 32:1-32:10. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603107.
  7. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. J. Algorithms, 41(2):280-301, 2001. URL: http://dx.doi.org/10.1006/jagm.2001.1186.
  8. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  9. Marek Cygan, Łukasz Kowalik, and Marcin Pilipczuk. Open problems from worker 2013, the workshop on kernels, April 2013. URL: http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf.
  10. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. On the hardness of losing width. Theory Comput. Syst., 54(1):73-82, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9480-1.
  11. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM, 61(4):23:1-23:27, 2014. URL: http://dx.doi.org/10.1145/2629620.
  12. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  13. Andrew Drucker. New limits to classical and quantum instance compression. In Proc. 53rd FOCS, pages 609-618, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.71.
  14. Michael Elberfeld, Martin Grohe, and Till Tantau. Where first-order and monadic second-order logic coincide. ACM Trans. Comput. Log., 17(4):25:1-25:18, 2016. URL: http://dx.doi.org/10.1145/2946799.
  15. Henning Fernau. Kernelization, Turing kernels. In Encyclopedia of Algorithms, pages 1043-1045. Springer, 2016. URL: http://dx.doi.org/10.1007/978-1-4939-2864-4_528.
  16. Fedor V. Fomin, Bart M. P. Jansen, and Michał Pilipczuk. Preprocessing subgraph and minor problems: When does a small vertex cover help? J. Comput. Syst. Sci., 80(2):468-495, 2014. URL: http://dx.doi.org/10.1016/j.jcss.2013.09.004.
  17. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and kernelization. In Proc. 28th STACS, pages 189-200, 2011. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2011.189.
  18. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar ℱ-Deletion: Approximation, kernelization and optimal FPT algorithms. In Proc. 53rd FOCS, pages 470-479, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.62.
  19. Fedor V. Fomin and Torstein J. F. Strømme. Vertex cover structural parameterization revisited. In Proc. 42nd WG, volume 9941 of LNCS, pages 171-182, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53536-3_15.
  20. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.007.
  21. Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219-242, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.09.002.
  22. Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. Uniform kernelization complexity of hitting forbidden minors. ACM Trans. Algorithms, 13(3):35:1-35:35, 2017. URL: http://dx.doi.org/10.1145/3029051.
  23. Jiong Guo and Rolf Niedermeier. Invitation to data reduction and problem kernelization. SIGACT News, 38(1):31-45, 2007. URL: http://dx.doi.org/10.1145/1233481.1233493.
  24. Gregory Gutin. Kernelization, constraint satisfaction problems parameterized above average. In Encyclopedia of Algorithms, pages 1011-1013. Springer, 2016. URL: http://dx.doi.org/10.1007/978-1-4939-2864-4_524.
  25. Bart M. P. Jansen and Hans L. Bodlaender. Vertex cover kernelization revisited - Upper and lower bounds for a refined parameter. Theory Comput. Syst., 53(2):263-299, 2013. URL: http://dx.doi.org/10.1007/s00224-012-9393-4.
  26. Bart M. P. Jansen and Astrid Pieterse. Polynomial kernels for hitting forbidden minors under structural parameterizations. CoRR, abs/1804.08885, 2018. URL: http://arxiv.org/abs/1804.08885.
  27. Bart M. P. Jansen, Venkatesh Raman, and Martin Vatshelle. Parameter ecology for feedback vertex set. Tsinghua Science and Technology, 19(4):387-409, 2014. URL: http://dx.doi.org/10.1109/TST.2014.6867520.
  28. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms, 12(2):21:1-21:41, 2016. URL: http://dx.doi.org/10.1145/2797140.
  29. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113:58-97, 2014. Google Scholar
  30. Stefan Kratsch. A randomized polynomial kernelization for vertex cover with a smaller parameter. In Proc. 24th ESA, volume 57 of LIPIcs, pages 59:1-59:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.59.
  31. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In Proc. 53rd FOCS, pages 450-459, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.46.
  32. Diptapriyo Majumdar. Structural parameterizations of feedback vertex set. In Proc. 11th IPEC, volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1-21:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.21.
  33. Diptapriyo Majumdar, Venkatesh Raman, and Saket Saurabh. Kernels for structural parameterizations of vertex cover - case of small degree modulators. In Proc. 10th IPEC, volume 43 of LIPIcs, pages 331-342, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.331.
  34. Neeldhara Misra. Kernelization, planar ℱ-Deletion. In Encyclopedia of Algorithms, pages 1033-1036. Springer, 2016. URL: http://dx.doi.org/10.1007/978-1-4939-2864-4_527.
  35. G.L. Nemhauser and L.E. Trotter (jr.). Vertex packings: structural properties and algorithms. Math. Program., 8:232-248, 1975. URL: http://dx.doi.org/10.1007/BF01580444.
  36. J. Nešetřil and P. Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27875-4.
  37. Michał Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. In Proc. 33rd STACS, volume 47 of LIPIcs, pages 57:1-57:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.57.
  38. Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Proc. 41st ICALP, pages 931-942, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_77.
  39. Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B, 41(1):92-114, 1986. URL: http://dx.doi.org/10.1016/0095-8956(86)90030-4.
  40. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Trans. Algorithms, 6(2), 2010. URL: http://dx.doi.org/10.1145/1721837.1721848.
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