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 , 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 . A combinatorial polynomial algorithm was found by Gy. Pap . 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 . A faster version of the algorithm of Pap, with running time [math]O(n^3 \log n)[/math], was developed by Babenko .

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 .