The independent even factor problem

ABSTRACT

This paper deals with the independent even factor problem, which generalizes both of the matching problem and the matroid intersection problem. For odd-cycle-symmetric digraphs, in which each arc in any odd dicycle has the reverse arc, a min-max formula is established as a common generalization of the Tutte-Berge formula for matchings and the min-max formula of Edmonds (1970) for matroid intersection. We devise a combinatorial efficient algorithm to find a maximum independent even factor in an odd-cycle-symmetric digraph, which commonly extends two of the alternating-path type algorithms, the even factor algorithm of Pap (2005) and the matroid intersection algorithms. This algorithm gives a constructive proof of the min-max formula, and contains a new operation on matroids, which corresponds to shrinking factor-critical components in the matching algorithm of Edmonds (1965). The running time of the algorithm is O(n⁴Q), where n is the number of vertices and Q is the time for an independence test. The algorithm also gives a common generalization of the Edmonds-Gallai decomposition for matchings and the principal partition for matroid intersection.

REFERENCES

• 1: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 2: W. H. Cunningham and J. F. Geelen, The optimal path-matching problem, Combinatorica, 17 (1997), pp. 315--337.
• 3: W. H. Cunningham and J. F. Geelen, Vertex-disjoint dipaths and even dicircuits, manuscript, 2001.
• 4: J. Edmonds, Paths, trees, and flowers, Can. J. Math., 17 (1965), pp. 449--467.
• 5: J. Edmonds, Submodular functions, matroids and certain polyhedra, Combinatorial Structures and Their Applications, New York, 1970, Gordon and Breach, pp. 69--87.
• 6: J. Edmonds, Matroid intersection, Ann. Discrete Math., 4 (1979), pp. 39--49.
• 7: A. Frank and L. Szegő, Note on the path-matching formula, J. Graph Theory, 41 (2002), pp. 110--119.
• 8: Nicholas J. A. Harvey, Algebraic Structures and Algorithms for Matching and Matroid Problems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.531-542, October 21-24, 2006 [doi>10.1109/FOCS.2006.8]
• 9: M. Iri, A review of recent work in Japan on principal partitions of matroids and their applications, Ann. New York Acad. Sci., 319 (1979), pp. 306--319.
• 10: M. Iri and S. Fujishige, Use of matroid theory in operations research, circuits and systems theory, Int. J. Syst. Sci., 12 (1981), 27--54.
• 11: E. L. Lawler, Matroid intersection algorithms, Math. Prog., 9 (1975), pp. 31--56.
• 12: G. Pap, A combinatorial algorithm to find a maximum even factor, Proc. 11th IPCO, LNCS 3509, Springer-Verlag, 2005, pp. 66--80.
• 13: Gyula Pap , László Szegö, On the maximum even factor in weakly symmetric graphs, Journal of Combinatorial Theory Series B, v.91 n.2, p.201-213, July 2004 [doi>10.1016/j.jctb.2004.01.001]
• 14: H. Perfect, Independence spaces and combinatorial problems, Proc. London Math. Society, 19 (1969), pp. 17--30.
• 15: A. Schrijver, Matroids and linking systems, J. Combin. Theory, Ser. B, 26 (1979), pp. 349--369.
• 16: B. Spille and L. Szegőo, A Gallai-Edmonds-type structure theorem for path-matchings, J. Graph Theory, 46 (2004), pp. 93--102.
• 17: Bianca Spille , Robert Weismantel, A Generalization of Edmonds' Matching and Matroid Intersection Algorithms, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.9-20, May 27-29, 2002
• 18: W. T. Tutte, The factorization of linear graphs, J. London Math. Society, 22 (1947), pp. 107--111.