# 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 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 [math]O(n^3 \log n)[/math], was developed by Babenko ^{[5]}.

## Independent even factors

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

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

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