A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph

We describe an algorithm for finding a minimum cost perfect two-matching in a weighted undirected graph, G = (V, E). The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. First, the degree constrained LP relaxation is posed as a bipartite two-matching problem and solved using a network flow algorithm. Next, the facet inducing two-matching cutset inequalities are activated selectively within a primal-dual framework that progressively eliminates half-integral values from the primal solution while maintaining dual feasibility. The algorithm is guaranteed to terminate in O(|V|²|E|) steps, although computational results suggest this upper bound to be pessimistic. The algorithm is experimentally shown to be effective on TSPLIB test problem^[1] ranging in size from 17 to 11,849 vertices.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.