TR-2003-01

A constrained independent set problem for matroids

Tamás Fleiner, András Frank, Satoru Iwata

Published in:
Operations Research Letters 32 (2004) 23-26

In this note, we study a constrained independent set problem for matroids and certain generalizations. The basic problem can be regarded as an ordered version of the matroid parity problem. By a reduction of this problem to matroid intersection, we prove a min-max formula. Studying the weighted case and a delta-matroid generalization, we prove that some of them are not more complex than matroid intersection, but others are as hard as matroid parity. We show how earlier results of Hefner and Kleinschmidt on so called MS-matchings fit in our framework. We also point out another connection to electric networks.

Bibtex entry:

@techreport{egres-03-01,

AUTHOR	=	{Fleiner, Tam{\'a}s and Frank, Andr{\'a}s and Iwata, Satoru},
TITLE	=	{A constrained independent set problem for matroids},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2003},
NUMBER	=	{TR-2003-01}

}