Document Open Access Logo

On Approximate Compressions for Connected Minor-Hitting Sets

Author M. S. Ramanujan

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.78.pdf
  • Filesize: 0.81 MB
  • 16 pages

Document Identifiers

Author Details

M. S. Ramanujan
  • University of Warwick, Coventry, UK

Cite AsGet BibTex

M. S. Ramanujan. On Approximate Compressions for Connected Minor-Hitting Sets. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.78

Abstract

In the Connected ℱ-Deletion problem, ℱ is a fixed finite family of graphs and the objective is to compute a minimum set of vertices (or a vertex set of size at most k for some given k) such that (a) this set induces a connected subgraph of the given graph and (b) deleting this set results in a graph which excludes every F ∈ ℱ as a minor. In the area of kernelization, this problem is well known to exclude a polynomial kernel subject to standard complexity hypotheses even in very special cases such as ℱ = K₂, i.e., Connected Vertex Cover. In this work, we give a (2+ε)-approximate polynomial compression for the Connected ℱ-Deletion problem when ℱ contains at least one planar graph. This is the first approximate polynomial compression result for this generic problem. As a corollary, we obtain the first approximate polynomial compression result for the special case of Connected η-Treewidth Deletion.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Approximation algorithms
Keywords
  • Parameterized Complexity
  • Kernelization
  • Approximation Algorithms

Metrics

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

References

  1. 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. Google Scholar
  2. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. URL: https://doi.org/10.1137/120880240.
  3. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  4. Holger Dell and Dániel Marx. Kernelization of packing problems. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 68-81, 2012. Google Scholar
  5. 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: https://doi.org/10.1145/2629620.
  6. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and ids. ACM Transactions on Algorithms, 11(2):13:1-13:20, 2014. Google Scholar
  7. Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science & Business Media, 2012. Google Scholar
  8. S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. Networks, 1(3):195-207, 1971. Google Scholar
  9. Andrew Drucker. New limits to classical and quantum instance compression. SIAM J. Comput., 44(5):1443-1479, 2015. Google Scholar
  10. Ding-Zhu Du, Yanjun Zhang, and Qing Feng. On better heuristic for euclidean steiner minimum trees (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 431-439, 1991. URL: https://doi.org/10.1109/SFCS.1991.185402.
  11. Eduard Eiben, Danny Hermelin, and M. S. Ramanujan. Lossy kernels for hitting subgraphs. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, pages 67:1-67:14, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.67.
  12. Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. Lossy kernels for connected dominating set on sparse graphs. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 29:1-29:15, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.29.
  13. Bruno Escoffier, Laurent Gourvès, and Jérôme Monnot. Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J. Discrete Algorithms, 8(1):36-49, 2010. URL: https://doi.org/10.1016/j.jda.2009.01.005.
  14. Samuel Fiorini, Gwenaël Joret, and Ugo Pietropaoli. Hitting diamonds and growing cacti. In Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings, pages 191-204, 2010. URL: https://doi.org/10.1007/978-3-642-13036-6_15.
  15. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and kernelization. SIAM J. Discrete Math., 30(1):383-410, 2016. URL: https://doi.org/10.1137/140997889.
  16. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. Google Scholar
  17. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-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, 2012. URL: https://doi.org/10.1109/FOCS.2012.62.
  18. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct pcps for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. Google Scholar
  19. Alexander Grigoriev and René Sitters. Connected feedback vertex set in planar graphs. In Graph-Theoretic Concepts in Computer Science, 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers, pages 143-153, 2009. URL: https://doi.org/10.1007/978-3-642-11409-0_13.
  20. Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (Turing) kernelization. Algorithmica, 71(3):702-730, 2015. Google Scholar
  21. Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 104-113, 2012. Google Scholar
  22. Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, and Stéphan Thomassé. Hitting and harvesting pumpkins. SIAM J. Discrete Math., 28(3):1363-1390, 2014. URL: https://doi.org/10.1137/120883736.
  23. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. Journal of Computer and System Sciences, 74(3):335-349, 2008. Google Scholar
  24. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113, 2014. Google Scholar
  25. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization-preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond, pages 129-161. Springer, 2012. Google Scholar
  26. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  27. Dániel Marx and Ildikó Schlotter. Obtaining a planar graph by vertex deletion. Algorithmica, 62(3-4):807-822, 2012. URL: https://doi.org/10.1007/s00453-010-9484-z.
  28. Jesper Nederlof. Fast polynomial-space algorithms using möbius inversion: Improving on steiner tree and related problems. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, pages 713-725, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_59.
  29. Geevarghese Philip, Venkatesh Raman, and Yngve Villanger. A quartic kernel for pathwidth-one vertex deletion. In Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers, pages 196-207, 2010. URL: https://doi.org/10.1007/978-3-642-16926-7_19.
  30. M. S. Ramanujan. An approximate kernel for connected feedback vertex set. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 77:1-77:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.77.
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 Imprint Privacy Contact