Constrained bipartite vertex cover: The easy kernel is essentially tight

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