A weighted independent even factor algorithm

作者：Takazawa Kenjiro^*

来源：Mathematical Programming, 2012, 132(1-2): 261-276.

DOI：10.1007/s10107-010-0397-z

• Independent even factor
• Combinatorial algorithm
• Dual integrality
• Nonbipartite matching
• Matroid intersection

An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n (3) gamma + n (6) m) time, where n and m are the number of vertices and edges, respectively, and gamma is the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n (4) gamma + n (5)) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection.

• 出版日期2012-4