A fast scaling algorithm for the weighted triangle-free 2-matching problem.

A perfect 2-matching in an undirected graph G = ( V , E ) is a function x : E → 0 , 1 , 2 such that for each node v ∈ V the sum of values x ( e ) on all edges e incident to v equals 2. If supp ( x ) = e ∈ E ∣ x ( e ) ≠ 0 contains no triangles then x is called triangle-free . Polyhedrally speaking, triangle-free 2-matchings are harder than 2-matchings, but easier than usual 1-matchings. Given edge costs c : E → R + , a natural combinatorial problem consists in finding a perfect triangle-free matching of minimum total cost. For this problem, Cornuéjols and Pulleyblank devised a combinatorial strongly-polynomial algorithm, which can be implemented to run in O ( V E log V ) time. (Here we write V , E to indicate their cardinalities | V | , | E | .) If edge costs are integers in range [ 0 , C ] then for both 1- and 2-matchings some faster scaling algorithms are known that find optimal solutions within O ( V α ( E , V ) log V E log ( V C ) ) and O ( V E log ( V C ) ) time, respectively, where α denotes the inverse Ackermann function. So far, no efficient cost-scaling algorithm is known for finding a minimum-cost perfect triangle-free2-matching. The present paper fills this gap by presenting such an algorithm with time complexity of O ( V E log V log ( V C ) ) . [ABSTRACT FROM AUTHOR]