2 Department of Mathematics and Statistics [Montréal]
We consider the <i>rank reduction problem</i> for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which admits a 2-approximation algorithm. In this paper we show that the rank reduction problem for transversal matroids is essentially at least as hard to approximate as the densest $k$-subgraph problem. We also prove that, while the problem is easily solvable in polynomial time for partition matroids, it is NP-hard when considering the intersection of two partition matroids. Our proof shows, in particular, that the maximum vertex cover problem is NP-hard on bipartite graphs, which answers an open problem of B. Simeone.
The maximum vertex coverage problem on bipartite graphs
1 Document citing this article
Source : OpenCitations
Bonnet, Ădouard; Cabello, Sergio, 2021, The Complexity Of Mixed-Connectivity, Annals Of Operations Research, 307, 1-2, pp. 25-35, 10.1007/s10479-021-04330-7.