Weighted restricted 2-matching

ISSN： 0025-5610

Source： Mathematical Programming, Vol.119, Iss.2, 2009-07, pp. : 305-329

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

A perfect 2-matching of a graph is a vector assigning values 0,1, or 2 to the edges such that the sum of values of edges incident with any node is equal to 2. For restricted perfect 2-matchings, we are also given a collection of “allowed” odd cycles, and restrict ourselves to those perfect 2-matchings the support of which contains no odd cycle not in this collection. Given a graph and a collection of allowed odd cycles, we provide a TDI description of the convex hull of restricted perfect 2-matchings. The description has large coefficients and is given implicitly, thus polynomial time separation or optimization is not straightforward. In order to have such an algorithm, one has to specify the collection of allowed odd cycles. For any fixed number k, we solve optimization in strongly polynomial time for the special cases when the collection consists of odd cycles of length less than k, or odd cycles of length more than k. These solved special cases include minimum weight perfect matching, minimum weight triangle-free and/or pentagon-free perfect perfect 2-matching, and a bunch of other relaxations of the travelling salesman problem. Our algorithm is based on a primal-dual approach, and the unweighted algorithm of Cornuéjols and Hartvigsen, which is used as a subroutine. The TDI description also may be regarded as a generalization of their unweighted min-max formula.