Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01349050
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, July 26, 2016 - 5:30:56 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:38 PM

File

2334-9777-1-PB.pdf
Explicit agreement for this submission

Identifiers

Collections

Citation

Gwenaël Joret, Adrian Vetta. Reducing the rank of a matroid. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.143-156. ⟨10.46298/dmtcs.2135⟩. ⟨hal-01349050⟩

Share

Metrics

Record views

28

Files downloads

826