Gwenaël Joret ; Adrian Vetta - Reducing the rank of a matroid

dmtcs:2135 - Discrete Mathematics & Theoretical Computer Science, September 16, 2015, Vol. 17 no.2 -
Reducing the rank of a matroidArticle

Authors: Gwenaël Joret 1; Adrian Vetta 2

  • 1 Département d'Informatique [Bruxelles]
  • 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.&nbsp;Simeone.

Volume: Vol. 17 no.2
Section: Discrete Algorithms
Published on: September 16, 2015
Submitted on: November 26, 2012
Keywords: maximum vertex cover,matroid,partial vertex cover,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

4 Documents citing this article

Consultation statistics

This page has been seen 464 times.
This article's PDF has been downloaded 679 times.