A weighted independent even factor algorithm (Q2429469)

This paper deals with the weighted independent even factor problem (WIEFP) in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via a valuated matroid intersection. This paper presents a primal-dual algorithm. The contribution of this paper is a combinatorial algorithm for the WIEFP in odd-cycle symmetric weighted digraphs. This algorithm commonly extends classical algorithms for the weighted matching and weighted matroid intersection problems, and works directly on the WIEFP. The time complexity of the algorithm is \(O(n^{4}\gamma+n^{5}).\) The algorithm finds an integer optimal solution for a linear program corresponding to the WIEFP, and simultaneously finds an integer optimal solution for the dual program if the weight is integer. Thus, it provides a new dual integrality theorem which commonly extends those for matching, matroid intersection, independent path-matching and even factors.