A weighted linear matroid parity algorithm

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Lovász (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem.

Authors

• Satoru Iwata 0001
• Yusuke Kobayashi 0001

Keywords

• Linear matroid parity
• Pfaffian
• matching
• polynomial-time algorithm
• primal-dual approach