Approximation Algorithms for the Minimum 2-edge Connected Spanning Subgraph Problem and the Graph-TSP in Regular Bipartite Graphs via Restricted 2-factors
Kenjiro Takazawa · 2015
In this paper, we address the minimum 2-edge connected spanning subgraph problem and the graph-TSP in regular bipartite graphs. For these problems, we present new approximation algorithms, each of whichnds a restricted 2-factor close to a Hamilton cycle in therst step. Werst prove that every regular bipartite graph of degree at least three has a square-free 2-factor. This immediately leads to 4 =3-approximation algorithms for the minimum 2-edge connected spanning subgraph problem and the graph-TSP in regular bipartite graphs. We then design a 7 =6-approximation algorithm for the minimum 2-edge connected spanning subgraph problem in 3-edge connected cubic bipartite graphs, which begins with a 2-factor intersecting all 3- and 4-edge cuts. This improves upon the previous best ratio due to Boyd, Iwata and Takazawa (2013), who designed a 6 =5-approximation algorithm for 3-edge connected cubic graphs. Our algorithm employs the ideas in this algorithm and makes use of bipartiteness to attain a better ratio 7 =6.