Improved Algorithms for Even Factors and Square‐Free Simple b‐Matchings

Given a digraph G=(VG,AG), an even 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 polynomially solvable. So far the only combinatorial algorithm known for this task is due to Pap; its running time is O(n ⁴) (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 ³logn)‐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.