Reducing the rank of a matroid
Gwenaël Joret, Adrian Vetta
Abstract
We consider the rank reduction problem 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 &rep; 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.
Full Text: PDF