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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.143-156
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01349050
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 17:30:56
Dernière modification le : jeudi 7 septembre 2017 - 01:03:48

Fichier

2334-9777-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01349050, version 1

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. 〈hal-01349050〉

Partager

Métriques

Consultations de la notice

33

Téléchargements de fichiers

219