A fast scaling algorithm for the weighted triangle-free 2-matching problem. (February 2018)

• Record Type: Journal Article
• Authors: Artamonov, S.; Babenko, M.
• Is Part Of: European journal of combinatorics. Volume 68(2018)
• Page Start: 3
• Page End: 23
• Publication Date: 2018-02
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.07.008
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 ) ) .