An algorithm for min-cost edge-disjoint cycles and its applications

The problems of finidng minimum-cost and maximum-cost sets of edge-disjoint cycles in a weighted undirected graph are studied. The importance of this problem is that it presents a ‘middle station’ in two reductions for planar graphs-one between the max-cut problem and that of max-weight matching, and the other between the Chinese Postman Problem and max-weight matching. The introduction of negative edge costs makes the reductions simple and efficient. New simpler algorithms are obtained for these two problems for planar graphs (where the max-weight matching problem can be solved very efficiently). The paper concludes that, in the case of planar weighted graphs (with arbitrary costs), all the three problems are mutually reducible and equivalent in terms of complexity.