# Partial vertex cover in bipartite graphs

In a bipartite graph, can we decide in polynomial time what is the maximum number of edges that can be covered by *k* nodes?

It was shown by Gwenaël Joret and Adrian Vetta ^{[1]} that this problem is NP-complete. Independently, the same result has been obtained by Nicola Apollonio and Bruno Simeone ^{[2]}. Apollonio and Simeone ^{[3]} also gave a 4/5-approximation alogrithm for the problem.

## Remarks

This question was asked by B. Simeone. In general graphs, the problem is in some sense more difficult than vertex cover: it was shown by Guo et al. ^{[4]} to be W[1]-complete (where *k* is the parameter), while Vertex cover is fixed parameter tractable.

It can also be seen that NP-hardness of the Partial vertex cover problem in bipartite graphs follows from the NP-completeness of the following problem, proved in ^{[5]}:

**Theorem ^{[5]}.**

*Given a bipartite graph and an integer t, it is NP-complete to decide if there is an edge set of size t that intersects every perfect matching.*

Indeed, if both classes of the graph have size *n*, then the answer for a given *t* is affirmative if and only if there exist *n-1* nodes that cover at least *m-t* edges.

## References

- ↑ G. Joret, A. Vetta,
*Reducing the rank of a matroid*, arXiv link - ↑ N. Apollonio, B. Simeone,
*The maximum vertex coverage problem on bipartite graphs*, DOI link - ↑ N. Apollonio, B. Simeone,
*Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs*, DOI link - ↑ J. Guo, R. Niedermeier, S. Wernicke,
*Parameterized complexity of vertex cover variants*, DOI link. Author link - ↑
^{5.0}^{5.1}R. Zenklusen, B. Ries, C. Picouleau, D. De Werra, M.-C. Costa, C. Bentz,*Blockers and transversals*, DOI link, author link