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 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 2k_a · k_b edges and 4k_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 ∈ (k_A) O¹(k_B), k'_B ∈ (k_B)^O(1), and |V(G')| ∈ O((k_B · 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(n^2-ε) bits, then NP ⊆ coNP/poly.