Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs (Q484552)

Given a graph \(G=(V,E)\), let \(2G\) denote the graph arising from \(G\) by doubling all its edges. For an even cardinality set \(T \subseteq V\), a \(T\)-join is a set \(F \subseteq E\) such that in the graph \((V,F)\), \(T\) is the set of vertices with odd degree. A \(T\)-tour in \(G\) is a \(T\)-join \(F\) in \(2G\) such that \((V,F)\) is connected. Given a connected graph \(G\) and an even cardinality set \(T \subseteq V\), the minimum \(T\)-tour problem is to find a \(T\)-tour in \(G\) of minimum cardinality \(\mathrm{opt}(G,T)\). If \(T=\emptyset\), \(F\) is called a tour, and the minimum \(T\)-tour problem is the well-known graph-TSP with optimal value \(\mathrm{opt}(G)\). If \(| T| =2\), say \(T=\{s,t\}\), the \(s\)-\(t\)-path graph TSP arises as a further special case. Finally, for a given \(2\)-edge-connected graph \(G\), the \(2\)-edge-connected subgraph problem 2ECSS is to find a \(2\)-edge-connected spanning subgraph of \(G\) with minimum number of edges \(\mathrm{opt}_{\text{2EC}}(G)\). \ The authors provide polynomial-time algorithms with approximation ratio \(7/5\) for the graph-TSP, \(3/2\) for the minimum \(T\)-tour problem (including the \(s,t\)-path graph-TSP), and \(4/3\) for the 2ECSS-problem. Based on a special kind of ear-decomposition optimized using forest representations of hypergraphs, the four main constructions can be resumed as follows:\newline i) a \(T\)-tour of cardinality at most \(3/2 \mathrm{opt}(G,T)+1/2\varphi-\pi\) (and at most \(3/2 \mathrm{opt}(G)-\pi\) if \(T=\emptyset\)) can be constructed in polynomial time, where \(\varphi\) and \(\pi\) are the number of even and of pendant ears in a suitable ear-decomposition. For the three approximation algorithms and the case when \(\pi\) is small, three different second constructions are presented: \newline ii) an inductive construction with respect to the ear-decomposition provides a \(T\)-tour of cardinality at most \(3/2 \mathrm{opt}(G,T)-1/2\varphi+\pi\), so that the smaller of the two \(T\)-tours has cardinality at most \(3/2 \mathrm{opt}(G,T)\); \newline iii) if \(T=\emptyset\), the second construction applies a lemma to the ear-decomposition, obtaining the bound \(4/3 \mathrm{opt}(G)+2/3\pi\); \newline iv) a simple induction with respect to the number of ears provides the bound \(5/4 \mathrm{opt}_{\text{2EC}}(G)+1/2\pi\) for 2ECSS.