LIPIcs.STACS.2016.45.pdf
- Filesize: 0.62 MB
- 13 pages
Document
Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight
Author
-
Part of:
Volume:
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-02-16
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
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.
Subject Classification
Keywords
- kernel lower bounds
- constrained bipartite vertex cover
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
-
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
-
R.C. Evans. Testing repairable RAMs and mostly good memories. In Proc. IEEE International Test Conference, pages 49-55, 1981.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
-
Marcin Pilipczuk. Banach’s algorithmic corner. http://corner.mimuw.edu.pl/?p=539, October 2013.
- 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.