Document Open Access Logo

An Approximate Kernel for Connected Feedback Vertex Set

Author M. S. Ramanujan

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.77.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

M. S. Ramanujan
  • University of Warwick, UK

Cite As Get BibTex

M. S. Ramanujan. An Approximate Kernel for Connected Feedback Vertex Set. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.77

Abstract

The Feedback Vertex Set problem is a fundamental computational problem which has been the subject of intensive study in various domains of algorithmics. In this problem, one is given an undirected graph G and an integer k as input. The objective is to determine whether at most k vertices can be deleted from G such that the resulting graph is acyclic. The study of preprocessing algorithms for this problem has a long and rich history, culminating in the quadratic kernelization of Thomasse [SODA 2010].
However, it is known that when the solution is required to induce a connected subgraph (such a set is called a connected feedback vertex set), a polynomial kernelization is unlikely to exist and the problem is NP-hard to approximate below a factor of 2 (assuming the Unique Games Conjecture).
In this paper, we show that if one is interested in only preserving approximate solutions (even of quality arbitrarily close to the optimum), then there is a drastic improvement in our ability to preprocess this problem. Specifically, we prove that for every fixed 0<epsilon<1, graph G, and k in N, the following holds:
There is a polynomial time computable graph G' of size k^O(1) such that for every c >= 1, any c-approximate connected feedback vertex set of G' of size at most k is a c * (1+epsilon)-approximate connected feedback vertex set of G.
Our result adds to the set of approximate kernelization algorithms introduced by Lokshtanov et al. [STOC 2017]. As a consequence of our main result, we show that Connected Feedback Vertex Set can be approximated within a factor min{OPT^O(1),n^(1-delta)} in polynomial time for some delta>0.

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. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem. SIAM J. Discrete Math., 12(3):289-297, 1999. URL: https://doi.org/10.1137/S0895480196305124.
  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. Google Scholar
  3. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Cross-Composition: A New Technique for Kernelization Lower Bounds. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 165-176, 2011. Google Scholar
  4. 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
  5. 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
  6. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 251-260, 2010. Google Scholar
  7. 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
  8. Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science & Business Media, 2012. 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. 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.
  15. 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
  16. 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.
  17. 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
  18. 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
  19. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113, 2014. Google Scholar
  20. 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
  21. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy Kernelization. CoRR, abs/1604.04111, 2016. URL: http://arxiv.org/abs/1604.04111.
  22. 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.
  23. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. J. Comb. Optim., 24(2):131-146, 2012. URL: https://doi.org/10.1007/s10878-011-9394-2.
  24. Stéphan Thomassé. A 4k^2 kernel for feedback vertex set. ACM Trans. Algorithms, 6(2):32:1-32:8, 2010. URL: https://doi.org/10.1145/1721837.1721848.
  25. Mihalis Yannakakis. The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems. J. ACM, 26(4):618-630, 1979. URL: https://doi.org/10.1145/322154.322157.
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