Document Open Access Logo

Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)

Authors Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, Ondrej Suchy

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.85.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Author Details

Archontia C. Giannopoulou
Daniel Lokshtanov
Saket Saurabh
Ondrej Suchy

Cite As Get BibTex

Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, and Ondrej Suchy. Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 85-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.85

Abstract

In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G \ S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPT^c for any constant c. In this paper we give an O(k^5) size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new  reduction rule, based on system of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.

Subject Classification

Keywords
  • Tree Deletion Set
  • Feedback Vertex Set
  • Kernelization
  • Linear Equations

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. Google Scholar
  2. Hans L. Bodlaender and Thomas C. van Dijk. A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst., 46(3):566-597, 2010. Google Scholar
  3. Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The undirected feedback vertex set problem has a poly(k) kernel. In Parameterized and Exact Computation - IWPEC, volume 4169 of LNCS, pages 192-202, 2006. Google Scholar
  4. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set new measure and new structures. In Algorithm Theory - SWAT 2010, volume 6139 of LNCS, pages 93-104, 2010. Google Scholar
  5. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci., 74(7):1188-1198, 2008. Google Scholar
  6. Robert Crowston, Michael R. Fellows, Gregory Gutin, Mark Jones, Frances A. Rosamond, Stéphan Thomassé, and Anders Yeo. Simultaneously satisfying linear equations over 𝔽₂: MaxLin2 and Max-r-Lin2 parameterized above average. In Foundations of Software Technology and Theoretical Computer Science - FSTTCS 2011, volume 13 of LIPIcs, pages 229-240, 2011. Google Scholar
  7. Robert Crowston, Gregory Gutin, Mark Jones, Eun Jung Kim, and Imre Z. Ruzsa. Systems of linear equations over 𝔽₂ and problems parameterized above average. In Algorithm Theory - SWAT 2010, volume 6139 of LNCS, pages 164-175, 2010. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  9. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In Foundations of Computer Science - FOCS 2012, pages 470-479, 2012. Google Scholar
  10. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Google Scholar
  11. Jiong Guo and Rolf Niedermeier. Invitation to data reduction and problem kernelization. SIGACT News, 38(1):31-45, 2007. Google Scholar
  12. Oscar H. Ibarra, Shlomo Moran, and Roger Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. J. Algorithms, 3(1):45-56, 1982. Google Scholar
  13. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  14. Stefan Kratsch. Polynomial kernelizations for MIN F^+Π and MAX NP. Algorithmica, 63(1-2):532-550, 2012. Google Scholar
  15. Stefan Kratsch and Magnus Wahlström. Preprocessing of Min Ones problems: A dichotomy. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, volume 6198 of Lecture Notes in Computer Science, pages 653-665. Springer, 2010. Google Scholar
  16. Stefan Kratsch and Magnus Wahlström. Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In Symposium on Discrete Algorithms - SODA 2012, pages 94-103, 2012. Google Scholar
  17. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In Foundations of Computer Science - FOCS 2012, pages 450-459, 2012. Google Scholar
  18. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization - preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond, volume 7370 of LNCS, pages 129-161, 2012. Google Scholar
  19. Dániel Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  20. Rolf Niedermeier. Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications). Oxford University Press, USA, March 2006. Google Scholar
  21. Venkatesh Raman, Saket Saurabh, and Ondřej Suchý. An FPT algorithm for tree deletion set. In Algorithms and Computation - WALCOM 2013, volume 7748 of LNCS, pages 286-297, 2013. Google Scholar
  22. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Transactions on Algorithms, 6(2), 2010. Google Scholar
  23. Magnus Wahlström. Abusing the Tutte matrix: An algebraic instance compression for the K-set-cycle problem. In Symposium on Theoretical Aspects of Computer Science - STACS 2013, volume 20 of LIPIcs, pages 341-352, 2013. Google Scholar
  24. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012, pages 887-898. ACM, 2012. Google Scholar
  25. Mihalis Yannakakis. The effect of a connectivity requirement on the complexity of maximum subgraph problems. J. ACM, 26(4):618-630, 1979. 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