Open Collections

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

Banff International Research Station for Mathematical Innovation and Discovery

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

Mathematics; Computer science; Operations research, mathematical programming; Operation research

video/mp4

Author affiliation: CNRS and Université Grenoble-Alpes

2019-04-03

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69421

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/