Finding 2-Factors Closer to TSP Tours in Cubic Graphs
Sylvia C. Boyd, Satoru Iwata, Kenjiro Takazawa · SIAM Journal on Discrete Mathematics · 2013
In this paper we are interested in algorithms for finding $2$-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained $2$-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight $2$-factor covering all the $3$-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the $3$- and $4$-edge cuts in bridgeless cubic graphs. Both of these algorithms run in ${\rm O}(n\sp{3})$ time, where $n$ is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time ${\rm O}(n\sp{3})$. We then improve this time complexity to ${\rm O}(n\sp{2} \log\sp{4}n)$ by relaxing the condition of the initial $2$-factor and elaborating on the subsequent processes.