# Even factor problem

Let D=(V,A) be a directed graph without loops. A path-cycle factor of D is a subgraph with in- and out-degree at most one in each node. In other words, every component is a path or a directed cycle.

An even factor is a path-cycle factor where every cycle component is even. The maximum even factor problem, introduced by Cunningham [1], consists of finding an even factor with the maximum number of arcs. It is NP-hard in general, but is polynomially solvable if D is odd-cycle symmetric, that is to say for every odd directed cycle the reverse cycle is also a subgraph of D.

A maximum even factor in a graph. An even factor of size 10 does not exist because the node on the right is a sink. The graph is not odd-cycle symmetric.

A polynomial algorithm can be obtained from the algebraic methods of Cunningham and Geelen; see the survey of Geelen [2]. A combinatorial polynomial algorithm was found by Gy. Pap [3]. This algorithm was extended to the maximum weight problem (when weights are odd-cycle-symmetric, i.e. weights of reversed odd cycles are the same) by Takazawa [4]. A faster version of the algorithm of Pap, with running time $O(n^3 \log n)$, was developed by Babenko [5].

## Independent even factors

Let D=(V,A) be a directed graph without loops, and let $M^{in}$ and $M^{out}$ be two matroids on ground set V. An even factor is independent if the nodes with in-degree 1 form an independent set in $M^{in}$, and the nodes of out-degree 1 form an independent set in $M^{out}$.

For odd-cycle-symmetric weights, the maximum weight independent even factor problem can be solved in polynomial time by the algebraic methods of Cunningham and Geelen, and a combinatorial algorithm was obtained by Takazawa [6].

## References

1. W. H. Cunningham, Matching, matroids, and extensions, DOI link
2. J. Geelen, An algebraic approach to matching problems, Citeseer link, author link
3. Gy. Pap, Combinatorial algorithms for matchings, even factors and square-free 2-factors, DOI link, Author link
4. K. Takazawa, A weighted even factor algorithm, DOI link, Technical Report
5. M.A. Babenko, Improved algorithms for even factors and square-free simple b-matchings, DOI link
6. K. Takazawa, A weighted independent even factor algorithm, DOI link, Technical Report