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
