Using large cycle covers to find small cycle covers in cubic graphs

A classic algorithm for the traveling salesman problem (TSP) on cubic graphs consists of finding a double spanning tree on the contracted graph of a cycle cover, where a cycle cover is defined as the set of edges in the complement of a perfect matching. If a cubic graph G on n vertices has a cycle cover containing k cycles, this results in a TSP tour of size $n+2k$. Since we are interested in short TSP tours, we would like to find cycle covers that have small size, i.e., having few connected components. Moemke and Svensson showed that a bridgeless, cubic graph contains a cycle cover consisting of at most n/6 cycles. Here we show how to use a large cycle cover to obtain a small cycle cover. In particular, if G is a bipartite, cubic graph on $n$ vertices, a cycle cover of size $(1/6+\epsilon)n$ can be used to find a cycle cover of size $(1/6 - \epsilon/2)n$. If G is a bridgeless, cubic graph on $n$ vertices, a cycle cover of size $(1/6 + \epsilon)n$ that covers all 3-edge cuts in G can be used to find a cycle cover of size $(1/6 - \epsilon/5)n$. (Joint work with Arash Haddadan.)Non UBCUnreviewedAuthor affiliation: CNRS and Université Grenoble-AlpesResearche