Geodesic
Reducing the rank of a matroid
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2015_17_2_a7,
     author = {Joret, Gwena\"el and Vetta, Adrian},
     title = {Reducing the rank of a matroid},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2015-2016},
     doi = {10.46298/dmtcs.2135},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2135/}
}
TY  - JOUR
AU  - Joret, Gwenaël
AU  - Vetta, Adrian
TI  - Reducing the rank of a matroid
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2135/
DO  - 10.46298/dmtcs.2135
LA  - en
ID  - DMTCS_2015_17_2_a7
ER  - 
%0 Journal Article
%A Joret, Gwenaël
%A Vetta, Adrian
%T Reducing the rank of a matroid
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2135/
%R 10.46298/dmtcs.2135
%G en
%F DMTCS_2015_17_2_a7
Joret, Gwenaël; Vetta, Adrian. Reducing the rank of a matroid. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2. doi : 10.46298/dmtcs.2135. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2135/

Cité par Sources :