Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators

Authors Diptapriyo Majumdar, Venkatesh Raman, Saket Saurabh



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.331.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Diptapriyo Majumdar
Venkatesh Raman
Saket Saurabh

Cite AsGet BibTex

Diptapriyo Majumdar, Venkatesh Raman, and Saket Saurabh. Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 331-342, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.IPEC.2015.331

Abstract

Vertex Cover is one of the most well studied problems in the realm of parameterized algorithms and admits a kernel with O(l^2) edges and 2*l vertices. Here, l denotes the size of a vertex cover we are seeking for. A natural question is whether Vertex Cover admits a polynomial kernel (or a parameterized algorithm) with respect to a parameter k, that is, provably smaller than the size of the vertex cover. Jansen and Bodlaender [STACS 2011, TOCS 2013] raised this question and gave a kernel for Vertex Cover of size O(f^3), where f is the size of a feedback vertex set of the input graph. We continue this line of work and study Vertex Cover with respect to a parameter that is always smaller than the solution size and incomparable to the size of the feedback vertex set of the input graph. Our parameter is the number of vertices whose removal results in a graph of maximum degree two. While vertex cover with this parameterization can easily be shown to be fixed-parameter tractable (FPT), we show that it has a polynomial sized kernel. The input to our problem consists of an undirected graph G, S \subseteq V(G) such that |S| = k and G[V(G)\S] has maximum degree at most 2 and a positive integer l. Given (G,S,l), in polynomial time we output an instance (G',S',l') such that |V(G')|<= O(k^5), |E(G')|<= O(k^6) and G has a vertex cover of size at most l if and only if G' has a vertex cover of size at most l'. When G[V(G)\S] has maximum degree at most 1, we improve the known kernel bound from O(k^3) vertices to O(k^2) vertices (and O(k^3) edges). In general, if G[V(G)\S] is simply a collection of cliques of size at most d, then we transform the graph in polynomial time to an equivalent hypergraph with O(k^d) vertices and show that, for d >= 3, a kernel with O(k^{d-epsilon}) vertices is unlikely to exist for any epsilon >0 unless NP is a subset of coNO/poly.
Keywords
  • Parameterized Complexity
  • Kernelization
  • expansion lemma
  • vertex cover
  • structural parameterization

Metrics

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

References

  1. Faisal N. Abu-Khzam. A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci., 76(7):524-531, 2010. 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. Google Scholar
  3. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. Google Scholar
  4. Leizhen Cai. Parameterized complexity of vertex colouring. Discrete Applied Mathematics, 127(3):415-429, 2003. Google Scholar
  5. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. Google Scholar
  6. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. On the hardness of losing width. Theory Comput. Syst., 54(1):73-82, 2014. Google Scholar
  7. 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. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  9. Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb., 34(3):541-566, 2013. Google Scholar
  10. Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, and Saket Saurabh. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst., 45(4):822-848, 2009. Google Scholar
  11. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and kernelization. In STACS, pages 189-200, 2011. Google Scholar
  12. Martin Grötschel and George L. Nemhauser. A polynomial algorithm for the max-cut problem on graphs without long odd cycles. Math. Programming, 29(1):28-40, 1984. Google Scholar
  13. Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. A probabilistic approach to problems parameterized above or below tight bounds. J. Comput. Syst. Sci., 77(2):422-429, 2011. Google Scholar
  14. Gregory Gutin and Anders Yeo. Constraint satisfaction problems parameterized above or below tight bounds: A survey. In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pages 257-286. Springer, 2012. Google Scholar
  15. Wen Lian Hsu, Yoshiro Ikura, and George L. Nemhauser. A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles. Math. Programming, 20(2):225-232, 1981. Google Scholar
  16. 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. Google Scholar
  17. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In FOCS, pages 450-459, 2012. Google Scholar
  18. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms, 11(2):15:1-15:31, 2014. Google Scholar
  19. George L. Nemhauser and Leslie E. Trotter Jr. Vertex packings: Structural properties and algorithms. Math. Program., 8(1):232-248, 1975. Google Scholar
  20. Michael Okun and Amnon Barak. A new approach for approximating node deletion problems. Inf. Process. Lett., 88(5):231-236, 2003. Google Scholar
  21. Fahad Panolan and Ashutosh Rai. On the kernelization complexity of problems on graphs without long odd cycles. In COCOON 2012, volume 7434 of LNCS, pages 445-457. Springer, 2012. Google Scholar
  22. Elena Prieto. Systematic kernelization in FPT algorithm design. PhD thesis, The University of Newcastle, Australia, 2005. Google Scholar
  23. Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997. Google Scholar
  24. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Transactions on Algorithms, 6(2), 2010. 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