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  that this problem is NP-complete. Independently, the same result has been obtained by Nicola Apollonio and Bruno Simeone . Apollonio and Simeone  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.  to be W-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 :
Theorem . 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.
- 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
- R. Zenklusen, B. Ries, C. Picouleau, D. De Werra, M.-C. Costa, C. Bentz, Blockers and transversals, DOI link, author link