Paper Info
Title
Reducing the rank of a matroid.
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 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.
Year
Venue
Keywords
2012
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
matroid,maximum vertex cover,partial vertex cover
Field
DocType
Volume
Integer,Matroid,Discrete mathematics,Combinatorics,Open problem,Bipartite graph,Matroid partitioning,Graphic matroid,Vertex cover,Time complexity,Mathematics
Journal
17.0
Issue
ISSN
Citations 
2.0
1462-7264
7
PageRank 
References 
Authors
0.49
9
2
Name
Order
Citations
PageRank
Gwenaël Joret119628.64
Adrian Vetta277857.85