## Invited Session Tue.3.H 3005

#### Tuesday, 15:15 - 16:45 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Matroid parity

**Chair: Tamás Király**

**Tuesday, 15:15 - 15:40 h, Room: H 3005, Talk 1**

**Ho Yee Cheung**

Algebraic algorithms for linear matroid parity problems

**Coauthors: Lap Chi Lau, Kai Man Leung**

**Abstract:**

We present faster and simpler algebraic algorithms for the linear matroid parity

problem and its applications. For the linear matroid parity problem, we obtain

a simple randomized algorithm with running time *O(mr*^{ω-1}), which

improves the *O(mr*^{ω})-time algorithm by Gabow and Stallmann. We also

present a very simple alternative algorithm with running time *O(mr*^{2}).

We further improve the algebraic algorithms for some specific graph problems

of interest.

We present faster randomized algorithms for the Mader's disjoint *S*-path

problem and the graphic matroid parity problem.

The techniques are based on the algebraic algorithmic framework developed by

Mucha, Sankowski and Harvey.

While linear matroid parity and Mader's disjoint *S*-path

are challenging generalizations for the design of combinatorial algorithms,

our results show that both the algebraic algorithms for linear

matroid intersection and graph matching can be extended nicely to

more general settings.

All algorithms are still faster than the existing algorithms even if fast matrix

multiplications are not used.

These provide simple algorithms that can be easily implemented.

**Tuesday, 15:45 - 16:10 h, Room: H 3005, Talk 2**

**Satoru Iwata**

Weighted linear matroid parity

**Abstract:**

The matroid parity problem was introduced as a common generalization of matching and matroid intersection problems.

In the worst case, it requires an exponential number of independence oracle calls.

Nevertheless, the problem is solvable if the matroid in question is represented by a matrix.

This is a result of Lovász (1980), who discovered a min-max theorem as well as a polynomial time algorithm.

Subsequently, more efficient algorithms have been developed for this linear matroid parity problem.

This talk presents a combinatorial, deterministic, strongly polynomial algorithm for its weighted version. The algorithm builds on a polynomial matrix formulation of the problem using Pfaffian and an augmenting path algorithm for the unweighted version by Gabow and Stallmann (1986).

Independently of this work, Gyula Pap has obtained the same result based on a different approach.

**Tuesday, 16:15 - 16:40 h, Room: H 3005, Talk 3**

**Gyula Pap**

Weighted linear matroid parity - A primal-dual approach

**Abstract:**

In the matroid parity problem we are given a matroid partitioned into pairs - subsets of cardinality 2. A set of pairs is called a matching if their union is an independent set. The (unweighted) matroid parity problem is to maximize the cardinality of a matching. This problem is solvable in polynomial time for linear matroids by Lovász' famous result - a generalization of graphical matching, and (linear) matroid intersection, both of which are solvable also in the weighted version. Thus one suspects the natural weighted version of linear matroid matching to also be tractable: consider a linear matroid whose elements are assigned weights, and partitioned into pairs - find a matching whose total weight is maximal. A solution to this problem would generalize both of Edmonds' algorithms, for matching, and for (linear) matroid intersection as well. In this talk a primal-dual algorithm is presented to solve weighted linear matroid matching in strongly polynomial time. A different solution to this problem has been found independently by Iwata.