Inverse Matroid Intersection Problem

LetM <Subscript>1</Subscript> andM <Subscript>2</Subscript> be matroids onS,B be theirk-element common independent set, andw a weight function onS. Given two functionsb ≥ 0 andc ≥ 0 onS, the Inverse Matroid Intersection Problem (IMIP) is to determine a modified weight functionw′ such that (a)B becomes a maximum weight common independent set of cardinalityk underw′, (b)c¦w′ — w¦ is minimum, and (c)¦w′ — w ≤ b. Many Inverse Combinatorial Optimization Problems can be considered as the special cases of the IMIP. In this paper we show that the IMIP can be solved in strongly polynomial time, and give a necessary and sufficient condition for the feasibility of the IMIP. Finally we extend the discussion to the version of the IMIP with Multiple Common Independent Sets. Copyright Physica-Verlag 1997