## 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 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^{1}(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.

Original language | English |
---|---|

Title of host publication | 33rd Symposium on Theoretical Aspects of Computer Science : STACS'16, February 17-20, 2016, Orléans, France |

Editors | N. Ollinger, H. Vollmer |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Number of pages | 12 |

ISBN (Print) | 9783959770019 |

DOIs | |

Publication status | Published - 1 Feb 2016 |

Event | 33rd Symposium on theoretical aspects of computer science (STACS 2016) - Orleans, France Duration: 17 Feb 2016 → 20 Feb 2016 Conference number: 33 |

### Publication series

Name | LIPICS |
---|---|

Publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, |

Volume | 47 |

ISSN (Electronic) | 1868-8969 |

### Conference

Conference | 33rd Symposium on theoretical aspects of computer science (STACS 2016) |
---|---|

Abbreviated title | STACS 2016 |

Country | France |

City | Orleans |

Period | 17/02/16 → 20/02/16 |

## Keywords

- Constrained Bipartite Vertex Cover
- Kernel lower bounds