Partial vertex cover in bipartite graphs

From Egres Open
Jump to: navigation, search

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

Solved b.jpg

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.


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.


  1. G. Joret, A. Vetta, Reducing the rank of a matroid, arXiv link
  2. N. Apollonio, B. Simeone, The maximum vertex coverage problem on bipartite graphs, DOI link
  3. N. Apollonio, B. Simeone, Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs, DOI link
  4. J. Guo, R. Niedermeier, S. Wernicke, Parameterized complexity of vertex cover variants, DOI link. Author link
  5. 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