Document Open Access Logo

Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size

Authors Huib Donkers , Bart M. P. Jansen , Michał Włodarczyk

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.14.pdf
  • Filesize: 1.08 MB
  • 18 pages

Document Identifiers

Author Details

Huib Donkers
  • Eindhoven University of Technology, The Netherlands
Bart M. P. Jansen
  • Eindhoven University of Technology, The Netherlands
Michał Włodarczyk
  • Eindhoven University of Technology, The Netherlands

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch).

Cite As Get BibTex

Huib Donkers, Bart M. P. Jansen, and Michał Włodarczyk. Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.14

Abstract

In the ℱ-Minor-Free Deletion problem one is given an undirected graph G, an integer k, and the task is to determine whether there exists a vertex set S of size at most k, so that G-S contains no graph from the finite family ℱ as a minor. It is known that whenever ℱ contains at least one planar graph, then ℱ-Minor-Free Deletion admits a polynomial kernel, that is, there is a polynomial-time algorithm that outputs an equivalent instance of size k^{𝒪(1)} [Fomin, Lokshtanov, Misra, Saurabh; FOCS 2012]. However, this result relies on non-constructive arguments based on well-quasi-ordering and does not provide a concrete bound on the kernel size.
We study the Outerplanar Deletion problem, in which we want to remove at most k vertices from a graph to make it outerplanar. This is a special case of ℱ-Minor-Free Deletion for the family ℱ = {K₄, K_{2,3}}. The class of outerplanar graphs is arguably the simplest class of graphs for which no explicit kernelization size bounds are known. By exploiting the combinatorial properties of outerplanar graphs we present elementary reduction rules decreasing the size of a graph. This yields a constructive kernel with 𝒪(k⁴) vertices and edges. As a corollary, we derive that any minor-minimal obstruction to having an outerplanar deletion set of size k has 𝒪(k⁴) vertices and edges.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • fixed-parameter tractability
  • kernelization
  • outerplanar graphs

Metrics

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

Related Versions

References

  1. Therese C. Biedl. Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs. Discret. Comput. Geom., 45(1):141-160, 2011. URL: https://doi.org/10.1007/s00454-010-9310-z.
  2. 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: https://doi.org/10.1145/2973749.
  3. Kevin Cattell, Michael J. Dinneen, Rodney G. Downey, Michael R. Fellows, and Michael A. Langston. On computing graph minor obstruction sets. Theor. Comput. Sci., 233(1-2):107-127, 2000. URL: https://doi.org/10.1016/S0304-3975(97)00300-9.
  4. Gary Chartrand and Frank Harary. Planar permutation graphs. Annales de l'I.H.P. Probabilités et statistiques, 3(4):433-438, 1967. Google Scholar
  5. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. Journal of Algorithms, 41(2):280-301, 2001. URL: https://doi.org/10.1006/jagm.2001.1186.
  6. David Coudert, Florian Huc, and Jean-Sébastien Sereni. Pathwidth of outerplanar graphs. J. Graph Theory, 55(1):27-41, 2007. URL: https://doi.org/10.1002/jgt.20218.
  7. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  8. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion. Algorithmica, 64(1):170-188, September 2012. Google Scholar
  9. Holger Dell and Dieter Van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM, 61(4), July 2014. URL: https://doi.org/10.1145/2629620.
  10. Guoli Ding and Stan Dziobiak. Excluded-minor characterization of apex-outerplanar graphs. Graphs Comb., 32(2):583-627, 2016. URL: https://doi.org/10.1007/s00373-015-1611-9.
  11. Michael J. Dinneen. Too many minor order obstructions. J. Univers. Comput. Sci., 3(11):1199-1206, 1997. URL: https://doi.org/10.3217/jucs-003-11-1199.
  12. Michael J. Dinneen, Kevin Cattell, and Michael R. Fellows. Forbidden minors to graphs with small feedback sets. Discret. Math., 230(1-3):215-252, 2001. URL: https://doi.org/10.1016/S0012-365X(00)00083-2.
  13. Michael J. Dinneen and Liu Xiong. Minor-order obstructions for the graphs of vertex cover 6. J. Graph Theory, 41(3):163-178, 2002. URL: https://doi.org/10.1002/jgt.10059.
  14. Huib Donkers, Bart M. P. Jansen, and Michał Włodarczyk. Preprocessing for outerplanar vertex deletion: An elementary kernel of quartic size, 2021. URL: http://arxiv.org/abs/2110.01868.
  15. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  16. Herbert J. Fleischner, Dennis P. Geller, and Frank Harary. Outerplanar graphs and weak duals. Journal of the Indian Mathematical Society, 38, 1974. URL: http://www.informaticsjournals.com/index.php/jims/article/view/16694.
  17. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and kernelization. SIAM J. Discret. Math., 30(1):383-410, 2016. URL: https://doi.org/10.1137/140997889.
  18. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar ℱ-deletion: Approximation, kernelization and optimal FPT algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470-479. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.62.
  19. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  20. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  21. Fabrizio Frati. Straight-line drawings of outerplanar graphs in O(dn log n) area. Computational Geometry, 45(9):524-533, 2012. URL: https://doi.org/10.1016/j.comgeo.2010.03.007.
  22. Emilio Di Giacomo, Giuseppe Liotta, and Tamara Mchedlidze. Lower and upper bounds for long induced paths in 3-connected planar graphs. Theor. Comput. Sci., 636:47-55, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.034.
  23. Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. Uniform kernelization complexity of hitting forbidden minors. ACM Trans. Algorithms, 13(3), March 2017. URL: https://doi.org/10.1145/3029051.
  24. Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michał Włodarczyk. Losing treewidth by separating subsets. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1731-1749. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.104.
  25. Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.68.
  26. Bart M. P. Jansen and Astrid Pieterse. Polynomial kernels for hitting forbidden minors under structural parameterizations. Theor. Comput. Sci., 841:124-166, 2020. URL: https://doi.org/10.1016/j.tcs.2020.07.009.
  27. Bart M. P. Jansen and Marcin Pilipczuk. Approximation and kernelization for chordal vertex deletion. SIAM J. Discret. Math., 32(3):2258-2301, 2018. URL: https://doi.org/10.1137/17M112035X.
  28. Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, and Stéphan Thomassé. Hitting and harvesting pumpkins. SIAM J. Discret. Math., 28(3):1363-1390, 2014. URL: https://doi.org/10.1137/120883736.
  29. Jens Lagergren. Upper bounds on the size of obstructions and intertwines. J. Comb. Theory, Ser. B, 73(1):7-40, 1998. URL: https://doi.org/10.1006/jctb.1997.1788.
  30. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
  31. J. Leydold and P. Stadler. Minimal cycle bases of outerplanar graphs. Electron. J. Comb., 5, 1998. Google Scholar
  32. Tamara Mchedlidze and Antonios Symvonis. Crossing-optimal acyclic hp-completion for outerplanar st-digraphs. J. Graph Algorithms Appl., 15(3):373-415, 2011. URL: https://doi.org/10.7155/jgaa.00231.
  33. Kerri Morgan and Graham Farr. Approximation algorithms for the maximum induced planar and outerplanar subgraph problems. J. Graph Algorithms Appl., 11(1):165-193, 2007. URL: https://doi.org/10.7155/jgaa.00141.
  34. Geevarghese Philip, Venkatesh Raman, and Yngve Villanger. A quartic kernel for pathwidth-one vertex deletion. In Dimitrios M. Thilikos, editor, Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers, volume 6410 of Lecture Notes in Computer Science, pages 196-207, 2010. URL: https://doi.org/10.1007/978-3-642-16926-7_19.
  35. Timo Poranen. Heuristics for the maximum outerplanar subgraph problem. J. Heuristics, 11(1):59-88, 2005. URL: https://doi.org/10.1007/s10732-005-6999-6.
  36. Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  37. Juanjo Rué, Konstantinos S. Stavropoulos, and Dimitrios M. Thilikos. Outerplanar obstructions for a feedback vertex set. Eur. J. Comb., 33(5):948-968, 2012. URL: https://doi.org/10.1016/j.ejc.2011.09.018.
  38. Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. An FPT-algorithm for recognizing k-apices of minor-closed graph classes. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 95:1-95:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.95.
  39. Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. k-apices of minor-closed graph classes. I. Bounding the obstructions. CoRR, abs/2103.00882, 2021. URL: http://arxiv.org/abs/2103.00882.
  40. Saket Saurabh. Open problems from the workshop on kernelization (WorKer 2019), 2019. URL: https://www.youtube.com/watch?v=vCjG5zGjQr4.
  41. Maciej M. Syslo. Characterizations of outerplanar graphs. Discret. Math., 26(1):47-53, 1979. URL: https://doi.org/10.1016/0012-365X(79)90060-8.
  42. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Trans. Algorithms, 6(2):32:1-32:8, 2010. URL: https://doi.org/10.1145/1721837.1721848.
  43. René Van Bevern, Hannes Moser, and Rolf Niedermeier. Approximation and tidying—a problem kernel for s-plex cluster vertex deletion. Algorithmica, 62(3):930-950, 2012. 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