Document Open Access Logo

Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight

Author Bart M. P. Jansen

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2016.45.pdf
  • Filesize: 0.62 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • kernel lower bounds
  • constrained bipartite vertex cover

Metrics

Abstract

The CONSTRAINED BIPARTITE VERTEX COVER problem asks, for a bipartite graph G with partite sets A and B, and integers k_A  and k_B, whether there is a vertex cover for G containing at most k_A vertices from A and k_B vertices from B. The problem has an easy kernel with 2 * k_A * k_B edges and 4 k_A * k_B vertices, based on the fact that every vertex in A of degree more than k_B has to be included in the solution, together with every vertex in B of degree more than k_A. We show that the number of vertices and edges in this kernel are asymptotically essentially optimal in terms of the product k_A * k_B. We prove that if there is a polynomial-time algorithm that reduces any instance (G,A,B,k_A,k_B) of CONSTRAINED BIPARTITE VERTEX COVER to an equivalent instance (G',A',B',k'_A,k'_B) such that k'_A in (k_A)^{O(1)}, k'_B in (k_B)^{O(1)}, and |V(G')| in O((k_A * k_B)^{1 - epsilon}), for some epsilon > 0, then NP subseteq coNP/poly and the polynomial-time hierarchy collapses. Using a different construction, we prove that if there is a polynomial-time algorithm that reduces any n-vertex instance into an equivalent instance (of a possibly different problem) that can be encoded in O(n^{2- epsilon}) bits, then NP subseteq coNP/poly.

Cite As Get BibTex

Bart M. P. Jansen. Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.45

Author Details

Bart M. P. Jansen

References

  1. Guoqiang Bai and Henning Fernau. Constraint bipartite vertex cover: simpler exact algorithms and implementations. J. Comb. Optim., 23(3):331-355, 2012. URL: http://dx.doi.org/10.1007/s10878-010-9289-7.
  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. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  3. 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: http://dx.doi.org/10.1137/120880240.
  4. Jianer Chen and Iyad A. Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. J. Comput. Syst. Sci., 67(4):833-847, 2003. URL: http://dx.doi.org/10.1016/j.jcss.2003.09.003.
  5. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. J. Algorithms, 41(2):280-301, 2001. URL: http://dx.doi.org/10.1006/jagm.2001.1186.
  6. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  7. Holger Dell and Dániel Marx. Kernelization of packing problems. In Proc. 23rd SODA, pages 68-81, 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.6.
  8. 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: http://dx.doi.org/10.1145/2629620.
  9. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  10. R.C. Evans. Testing repairable RAMs and mostly good memories. In Proc. IEEE International Test Conference, pages 49-55, 1981. Google Scholar
  11. Michael R. Fellows, Bart M. P. Jansen, and Frances Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European J. Combin., 34(3):541-566, 2013. URL: http://dx.doi.org/10.1016/j.ejc.2012.04.008.
  12. Henning Fernau and Rolf Niedermeier. An efficient exact algorithm for constraint bipartite vertex cover. J. Algorithms, 38(2):374-410, 2001. URL: http://dx.doi.org/10.1006/jagm.2000.1141.
  13. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.007.
  14. Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proc. 23rd SODA, pages 104-113, 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.9.
  15. Bart M. P. Jansen. On sparsification for computing treewidth. Algorithmica, 71(3):605-635, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9924-2.
  16. Stefan Kratsch, Geevarghese Philip, and Saurabh Ray. Point line cover: The easy kernel is essentially tight. In Proc. 25th SODA, pages 1596-1606. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.116.
  17. S.-Y. Kuo and W.K. Fuchs. Efficient spare allocation for reconfigurable arrays. IEEE Design Test of Computers, 4(1):24-31, 1987. URL: http://dx.doi.org/10.1109/MDT.1987.295111.
  18. Marcin Pilipczuk. Banach’s algorithmic corner. http://corner.mimuw.edu.pl/?p=539, October 2013. Google Scholar
  19. Chee-Keng Yap. Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci., 26:287-300, 1983. URL: http://dx.doi.org/10.1016/0304-3975(83)90020-8.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact