Source-linked AI summary
Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
András Sebő, Jens Vygen
TL;DR
The paper develops polynomial-time approximation algorithms for graphic TSP and related connectivity problems, addressing longstanding gaps in their guarantees. Its approach combines optimized ear-decompositions with parity correction, yielding ratios of 7/5 for graphic TSP, 3/2 for connected-T-join, and 4/3 for 2-edge-connected spanning subgraphs.
Problem
The paper studies how to improve approximation guarantees for graphic TSP and related 2-edge-connected and connected-T-join problems.
Method
The algorithms construct optimized ear-decompositions and combine connectivity-oriented structures with parity correction, including edge deletions that preserve connectivity.
Results
The paper reports ratios of 7/5 for graphic TSP, 3/2 for connected-T-join, and 4/3 for finding a smallest 2-edge-connected spanning subgraph.
Takeaways & Limitations
The methods provide improved approximation guarantees across graphic TSP and related problems, while also supplying lower bounds from LP relaxations used to derive those ratios.
Takeaways & Limitations
Variants that forbid doubled edges have no approximation algorithms unless P = NP, because they include Hamiltonian circuit as a special case in 3-regular graphs.
Abstract
from arXiv · showhide
We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graphic TSP itself, we improve the approximation ratio to 7/5. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the graphic $s$-$t$-path-TSP as a special case. Our improved approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.
1 Introduction
The paper studies approximation algorithms for graphic TSP, connected-T-joins, and 2ECSS, improving guarantees through optimized ear-decompositions and related constructions. It also develops LP-based lower bounds supporting these ratios.
- Problems: Graphic TSP asks for a shortest Hamiltonian circuit, minimum closed walk in 2G, or minimum connected-∅-join; these formulations are equivalent.
- Problems: Connected-T-join generalizes the graphic s-t-path-TSP by seeking a minimum connected-T-join for any even-cardinality terminal set T.
- Problems: The related 2ECSS problem seeks a minimum-edge 2-edge-connected spanning subgraph, and any tour yields a 2ECSS with no more edges.
- Our results and methods: 7/5 is the paper’s approximation ratio for graphic TSP, while 3/2 applies to connected-T-joins and includes graphic s-t-path-TSP.
- Our results and methods: 4/3 is the approximation ratio obtained for 2ECSS.
- Our results and methods: Optimized ear-decompositions separate connectivity and parity, combine with parity-correction edge deletions, and support polynomial-time constructions and LP lower bounds.
2 Ear-Decompositions
The section develops ear-decompositions and specializes them into nice decompositions where short ears are pendant and structurally separated. These decompositions support bounds for T-joins and connected-T-joins through parity-aware processing of pendant ears.
- Ear-decompositions: An ear-decomposition starts from one vertex and adds circuits or paths sharing one or two existing endpoints.Open decompositions require all ears after the first to be open.
- Ear-decompositions: 2-edge-connected graphs are exactly the graphs admitting ear-decompositions, while open ear-decompositions characterize 2-vertex-connected graphs.The number of ears is |E(G)| − |V(G)| + 1.
- Even and short ears: Minimizing nontrivial ears is equivalent to the 2ECSS problem because deleting 1-ears preserves 2-edge-connectivity.Pendant ears are nontrivial ears with no nontrivial ear attached to them.
- Even and short ears: The parameter ϕ(G) is the minimum number of even ears in an ear-decomposition and is computable in polynomial time.Even ears determine lower bounds for T-joins and 2-edge-connected spanning subgraphs.
- Even and short ears: Short ears are 2-ears and 3-ears; unlike even ears, their number is not known to be efficiently minimizable, so the construction instead makes them pendant.All short ears used here are open except possibly the first ear.
- Bounds from pendant ears: Processing pendant ears in reverse order yields universal upper bounds for T-joins and connected-T-joins, with parity and short-ear status controlling the edge counts.The construction alternates subpaths by T-vertices and selects or doubles subpath edges to preserve the required parity and connectivity.
- Nice ear-decompositions: A nice ear-decomposition has pendant short ears whose internal vertices are non-adjacent across different short ears, forming an eardrum structure.Lemma 10 guarantees such a decomposition for every 2-vertex-connected graph in O(|V(G)||E(G)|) time.
3 Earmuffs
Earmuffs select compatible paths through eardrum components so their union is a forest, maximizing the number of short-ear structures handled together. The maximum can be computed in polynomial time using matroid intersection or forest representative systems.
- Earmuffs: For each eardrum component, the method chooses a path whose internal vertices are that component and seeks to minimize additional edges needed for connectivity.If the selected paths form a forest, the remaining connectivity cost is determined by its components.
- Earmuffs: An earmuff is a set of one path per selected eardrum component whose union is a forest; a maximum earmuff maximizes the number of selected components.Its size is denoted by µ(G, M).
- Algorithms: A maximum earmuff can be found in polynomial time through matroid intersection, while forest representative systems provide a more elementary and faster algorithmic route.The latter approach uses augmenting searches over a directed graph and runs in O(|V(G)||E(G)|) time.
- Matroid intersection: The path-selection problem is represented by choosing distinct edges from endpoint sets so that the chosen edges form a forest in the complete graph on non-eardrum vertices.This connects the problem to the cycle matroid and Rado’s theorem.
- Forest representatives: The maximum earmuff size equals the maximum number of eardrum components admitting a forest representative system, and such a representative system can be converted into an earmuff.The conversion takes O(|V(G)|^2) time.
4 Lower Bounds
The section derives lower bounds for connected-T-joins and 2-edge-connected spanning subgraphs from ear parameters, eardrums, earmuffs, and LP relaxations. The earmuff quantity Lµ provides a shared lower-bound framework for these problems.
- Even-ear lower bounds: The even-ear parameter Lϕ(G) lower-bounds the number of edges in every 2-edge-connected spanning subgraph and therefore satisfies Lϕ(G) ≤ OPT2EC(G).The proof uses a T-join supplied by Frank’s theorem and a corresponding family of T-cuts.
- Connected-T-join bounds: LP(G) is not a valid lower bound for connected-T-joins, so the analysis combines Proposition 3 with the earmuff theorem to obtain an LP(G, T)-based bound.This distinguishes the connected-T-join lower-bound framework from the ordinary subtour relaxation.
- Earmuff lower bounds: The quantity Lµ(G, M) = |V(G)| − 1 + |M| − µ(G, M) is a lower bound on LP(G, T) when the eardrum avoids T.The assumptions require Pf to be nonempty for every f in M and VM ∩ T = ∅.
- Earmuff lower bounds: Every connected-T-join has at least Lµ(G, M) edges, and the same quantity lower-bounds every 2-edge-connected spanning subgraph under the stated eardrum conditions.These bounds are obtained through partition-based cut arguments and feasible LP solutions.
- Exact characterization: For a nice ear-decomposition, Lµ(G, M) is exactly the minimum size of a connected spanning subgraph of 2G whose vertices in VM all have even degree.A maximum earmuff supplies the selected paths, and additional edges connect their components.
5 Approximation Algorithms
The algorithms use optimized nice ear-decompositions and obtain improved guarantees for connected-T-joins, graphic TSP, and 2ECSS. Their bounds are supported by LP lower bounds and tight examples.
- Common framework: All approximation algorithms begin by computing a suitable ear-decomposition, including a polynomial-time construction with a maximum earmuff.The decomposition is optimized through forest-representation techniques and related polynomial-time methods.
- Connected-T-joins: 3/2-approximation for connected-T-joins is achieved in O(|V (G)|3) time, with a solution of cardinality at most 3/2 LP(G, T).The result applies to every connected graph and even-cardinality terminal set T.
- Graphic TSP: 7/5-approximation for graphic TSP is achieved in O(|V (G)|3) time, producing a tour of cardinality at most 7/5 LP(G).The shorter of two constructed tours supplies the stated bound.
- 2ECSS: 4/3-approximation is obtained for the minimum 2-edge-connected spanning subgraph problem.The algorithm compares two constructions, including one derived from the connected-T-join framework.
6 Remarks on Integrality Ratios
The remarks characterize LP integrality ratios for connected T-joins, tours, and 2-edge-connected spanning subgraphs, and relate these ratios to approximation guarantees. They also give matching or near-matching bounds and a reduction linking 2ECSS to graphic TSP.
- 2ECSS: The 2ECSS polyhedron has unit integrality ratio at most 4/3.Its integer vectors correspond to 2-edge-connected spanning subgraphs of the doubled graph, and Theorem 30 supplies the upper bound.
- Graphic versus general metrics: For graphic weight functions, the subtour-polytope integrality ratio is at most 7/5, whereas no bound better than 3/2 is known for general metric weights.The graphic bound follows from Corollary 33; the general-metric comparison is attributed to Wolsey.
- Relation between 2ECSS and graphic TSP: A ρ-approximation for 2ECSS yields a 2/3(ρ + 1)-approximation for graphic TSP.The same relationship applies to the corresponding unit integrality ratios of the relevant polyhedra.