Constrained bipartite vertex cover: The easy kernel is essentially tight

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
1 Downloads (Pure)

Abstract

The CONSTRAINED BIPARTITE VERTEX COVER problem asks, for a bipartite graph G with partite sets A and B, and integers kA and kB, whether there is a vertex cover for G containing at most kA vertices from A and kB vertices from B. The problem has an easy kernel with 2ka · kb edges and 4kA · kb vertices, based on the fact that every vertex in A of degree more than kB has to be included in the solution, together with every vertex in B of degree more than kA. We show that the number of vertices and edges in this kernel are asymptotically essentially optimal in terms of the product kA· kB. We prove that if there is a polynomial-time algorithm that reduces any instance (G,A,B, kA, kB) of CONSTRAINED BIPARTITE VERTEX COVER to an equivalent instance (G', A', B', k'A, k'B) such that k'A ∈ (kA) O1(kB), k'B ∈ (kB)O(1), and |V(G')| ∈ O((kB · kB)1 -ε), for some ε > 0, then NP ⊆ 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(n2-ε) bits, then NP ⊆ coNP/poly.

Original languageEnglish
Title of host publication33rd Symposium on Theoretical Aspects of Computer Science : STACS'16, February 17-20, 2016, Orléans, France
EditorsN. Ollinger, H. Vollmer
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Print)9783959770019
DOIs
Publication statusPublished - 1 Feb 2016
Event33rd Symposium on theoretical aspects of computer science (STACS 2016) - Orleans, France
Duration: 17 Feb 201620 Feb 2016
Conference number: 33

Publication series

NameLIPICS
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH,
Volume47
ISSN (Electronic)1868-8969

Conference

Conference33rd Symposium on theoretical aspects of computer science (STACS 2016)
Abbreviated titleSTACS 2016
CountryFrance
CityOrleans
Period17/02/1620/02/16

Keywords

  • Constrained Bipartite Vertex Cover
  • Kernel lower bounds

Fingerprint Dive into the research topics of 'Constrained bipartite vertex cover: The easy kernel is essentially tight'. Together they form a unique fingerprint.

Cite this