Given ad igraphG = (V G, AG) ,a neven factor M ⊆ AG is a set formed by node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geelen and Cunningham and generalize path matchings in undirected graphs. Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard but for the class of odd-cycle symmetric digraphs the problem is polyno- mially solvable. So far the only combinatorial algorithm known for this task is due to Pap; its running time is O(n 4 ) (hereinafter n denotes the number of nodes in G and m denotes the number of arcs or edges). In this paper we introduce a novel sparse recovery technique and devise an O(n 3 log n)-time algorithm for finding a maximum cardinality even factor in an odd- cycle symmetric digraph. Our technique also applies to other similar problems, e.g. finding a maximum cardinality square-free simple b-matching.
['Maxim A. Babenko']
Improved Algorithms for Even Factors and Square-Free Simple b-Matchings