Robust Matchings and Matroid Intersections
Ryo Fujita, Yusuke Kobayashi, Kazuhisa Makino · SIAM Journal on Discrete Mathematics · 2013
In a weighted independence system, an independent set is said to be $\alpha$-robust if, for all $p$, the total weight of its heaviest $p$ elements is at least $\alpha$ times the maximum weight of a $p$-independent set. Here a $p$-independent set is an independent set with at most $p$ elements. The set of matchings in a weighted graph is a typical example of a weighted independence system, and Hassin and Rubinstein [SIAM J. Discrete Math., 15 (2002), pp. 530--537] showed that every graph has a $\frac{1}{\sqrt2}$-robust matching and it can be found by a $k$th power algorithm in polynomial time. In this paper, we show that it can be extended to the matroid intersection problem; i.e., there always exists a $\frac{1}{\sqrt2}$-robust matroid intersection, which is polynomially computable. We also study the time complexity of the robust matching problem. We show that a 1-robust matching can be computed in polynomial time (if one exists), and, for any fixed number $\alpha$ with $\frac{1}{\sqrt2}0$, there exists a weighted graph such that no $k$th power algorithm outputs a $(\frac{1}{\sqrt2}+\epsilon)$-approximation for computing the most robust matching.