Optimal Matching Forests and Valuated Delta-Matroids
Kenjiro Takazawa · SIAM Journal on Discrete Mathematics · 2014
The matching forest problem in mixed graphs is a common generalization of the matching problem in undirected graphs and the branching problem in directed graphs. Giles presented an $\mathrm{O}(n^{2}m)$-time algorithm for finding a maximum-weight matching forest, where $n$ is the number of vertices and $m$ is that of edges, and a linear system describing the matching forest polytope. Later, Schrijver proved total dual integrality of the linear system. In the present paper, we reveal another nice property of matching forests: the degree sequences of the matching forests in any mixed graph form a delta-matroid, and the weighted matching forests induce a valuated delta-matroid. We remark that the delta-matroid is not necessarily even, and the valuated delta-matroid induced by weighted matching forests slightly generalizes the well-known notion of Dress and Wenzel's valuated delta-matroids. By focusing on the delta-matroid structure and reviewing Giles' algorithm, we design a simpler $\mathrm{O}(n^{2}m)$-time algorithm for the weighted matching forest problem. By incorporating Gabow's method for the weighted matching problem into Giles' algorithm, we also present a faster algorithm for the weighted matching forest problem running in $\mathrm{O}(n^{3})$-time, which improves upon the previous best complexity of $\mathrm{O}(n^{2}m)$.