Approximating Graphic TSP by Matchings

1 Introduction

• Graph-TSP asks for a minimum-edge Eulerian multigraph in an unweighted graph and remains APX-hard, while the Held-Karp integrality gap was bounded between 4/3 and 3/2.The introduction presents improving the gap as a route toward better metric-TSP guarantees.Source: §1 · p. 1
• For graphs whose blocks are claw-free or have degree at most 3, the framework gives a 4/3-approximation and matches the conjectured Held-Karp integrality gap.For 2-vertex-connected subcubic graphs, it also gives a spanning Eulerian multigraph with at most 4n/3 − 2/3 edges, settling a conjecture of Boyd et al..Source: §1 · p. 2
• Unlike earlier approaches that add matching edges, the framework can remove selected edges while preserving connectivity, reducing the cost of an Eulerian solution.The authors identify finding a sufficiently large removable set as a central challenge.Source: §1 · p. 2
• The analysis reduces finding removable edges to a minimum-cost circulation problem and uses properties of extreme-point Held-Karp solutions.The circulation network’s simpler structure in special graph classes supports better guarantees there.Source: §1 · pp. 2–3
• For graphic-metric traveling-salesman paths with prespecified endpoints, the framework gives a ratio below 3 − 2/3 + ε, and 1.5 + ε when each block is degree-three bounded.The paper states these guarantees for every ε > 0.Source: §1 · p. 3

Held-Karp Relaxation

• For graph-TSP, the Held-Karp relaxation can be restricted to input-graph edges, and its known integrality gap lies between 4/3 and 3/2.A 4/3 lower-bound instance is claw-free and has degree at most 3.Source: §2 · p. 3
• A graph-TSP approximation for each 2-vertex-connected subgraph extends to the whole connected graph with the same guarantee.The reduction recursively solves the subgraphs induced by each component after deleting a cut vertex; their LP lower bounds sum to at most the original bound.Source: §2 · pp. 3–4

Matchings of Cubic 2-Edge-Connected Graphs

• For cubic 2-edge-connected graphs, a polynomial-size distribution over perfect matchings can be found in which each edge is selected with probability 1/3.This follows from the perfect-matching polytope description and a polynomial-time convex decomposition.Source: §2 · p. 4

3 Approximation Framework

• A removable pairing groups disjoint pairs of removable edges incident to a common vertex of degree at least 3, with connectivity preserved when at most one edge per pair is deleted.The paired-edge condition lets the construction control which removals preserve a connected graph.Source: §3 · pp. 4–5
• 4/3|E| − 2/3|R| edges suffice for a spanning Eulerian multigraph in a 2-vertex-connected graph with removable pairing (R, P).The theorem gives a polynomial-time algorithm for constructing the multigraph.Source: §3 · p. 5
• The matching construction replaces non-cubic vertices with gadgets, applies cubic-graph matching sampling, and restricts the resulting matching to the original edges.The gadgets preserve 2-vertex-connectivity, and each original edge is selected with probability 1/3.Source: §3 · p. 5
• The selected matching edges toggle vertex-degree parity; removing the removable ones and adding the rest produces a connected Eulerian multigraph.The expected edge count is 4/3|E| − 2/3|R|, and the finite distribution allows the construction to be derandomized.Source: §3 · p. 6

• A depth-first-search tree orients tree-edges toward leaves and back-edges toward the root; child-specific vertices split tree-arcs and receive redirected back-arcs.The construction distinguishes new in-vertices from old out-vertices.Source: §4 · p. 6
• Tree-arcs have demand 1, other arcs demand 0, and each in-vertex accepts one unit of incoming back-arc circulation at no cost.Additional circulation on those back-arcs contributes to the piecewise-linear cost.Source: §4 · p. 7
• A minimum-cost circulation of cost c(C*) yields a spanning Eulerian multigraph with at most 4/3n + 2/3c(C*) - 2/3 edges.Source: §4 · p. 7
• The proof uses integral circulation support to construct a 2-vertex-connected subgraph and define a removable pairing that preserves connectivity after edge removals.Flow conservation and the gadget design establish connectivity; the pairing then satisfies the removable-pairing conditions.Source: §4 · pp. 7–8
• The pairing’s size is related to circulation cost, allowing the Eulerian edge bound to account for removable edges rather than only added edges.The proof derives |R| − 2|P| ≤ c(C*) + 1 before applying the pairing bound.Source: §4 · p. 8

5 Improved Approximation Algorithms

• The section’s framework is applied first to restricted graph classes and then to general graphs to obtain improved approximation algorithms.For general graphs, the analysis restricts attention to 2-vertex-connected graphs with at most 2n − 1 edges and uses a circulation to construct a spanning Eulerian multigraph.Source: §5 · p. 8, §5.2 · p. 9

5.1 Bounded Degree and Claw-Free Graphs

• For a 2-vertex-connected graph, Lemma 5.1 constructs in polynomial time a spanning Eulerian multigraph with at most 4n/3 − 2/3 edges.The proof uses a depth-first search tree and a circulation network; bounded degree limits the circulation cost.Source: §5.1 · pp. 8–9
• For graphs whose blocks are degree-three-bounded or claw-free, the framework gives a 4/3-approximation and an upper bound of 4/3 on the Held-Karp integrality gap.A 2-vertex-connected graph has a spanning Eulerian multigraph with at most 4n/3 − 2/3 edges; the argument also gives a bound for connected graphs decomposed into such blocks.Source: §5.1 · pp. 8–9

5.2 General Graphs

• At OPTLP (G) = n, Algorithm 1 has approximation guarantee 1.4477; its guarantee worsens as OPTLP (G) increases, while Christofides’ guarantee improves.The algorithm uses Algorithm 1 when OPTLP (G) is close to n and Christofides’ algorithm otherwise.Source: §5.2 · p. 12, Figure 4 · p. 12

6 The Traveling Salesman Path Problem

• The section develops a sequence of modifications and generalizations of the graph-TSP techniques to obtain approximation algorithms for the traveling salesman path problem on graphic metrics.Source: §6 · p. 13

6.1 Using Held-Karp for Graph-TSPP

• The Held–Karp relaxation for graph-TSPP distinguishes cuts that separate s and t from cuts that do not, and its hardest instances reduce to 2-vertex-connected graphs.The relaxation is denoted OPTLP(G, s, t), with OPTLP(G) = OPTLP(G, s, s).Source: §6.1 · p. 13

6.2 Generalization of the Approximation Framework to graph-TSPP

• For a 2-vertex-connected graph with a removable pairing, the generalized framework constructs an Eulerian s–t path using at most 4/3|E| − 2/3|R| + dist(s, t)/3 edges.The section treats graph-TSP as the special case where dist(s, t) = 0.Source: §6.2 · p. 14

• The framework achieves a graph-TSP approximation ratio below 1.461 and a tight Held–Karp integrality-gap bound for a restricted class containing degree-three-bounded and claw-free graphs.In subcubic 2-vertex-connected graphs, it yields a graph-TSP solution with at most 4n/3 − 2/3 edges, settling a conjecture from.Source: §7 · p. 16
• For graph-TSPP on graphic metrics with prescribed endpoints, the framework guarantees a ratio below 1.586, approaching 1.5 for degree-three-bounded graphs.Source: §7 · p. 17
• For general metrics, finding a sufficiently large removable pairing to improve on Christofides’ algorithm remains open.Source: §7 · p. 17

• The circulation network C(G, T) is shown for a graph G with depth-first tree T.Source: Figure 7 · p. 19
• In-vertices are white and out-vertices are black in the network illustration.Source: Figure 7 · p. 19
• The figure distinguishes the two vertex types within the circulation network built from the depth-first tree.Source: Figure 7 · p. 19

• An algorithm achieving cost at most r · OPTLP on 2-vertex-connected subgraphs extends to all graphs with the same guarantee and polynomial running time.Source: §B.1 · p. 19
• The extension recursively splits at cut vertices, solves the resulting subinstances, and unions their solutions.Source: §B.1 · p. 20
• The proof establishes feasibility by combining subproblem Eulerian paths and bounds the sum of their LP optima by the original instance’s LP optimum.Source: §B.1 · p. 20

B.2 Maximum Profit to Size Ratio

• The section defines f(T) and considers its first derivative to locate the maximum.The derivative is written explicitly in the passage.Source: §B.2 · p. 20
• Setting the derivative condition to zero yields T^2 − 4T + 2 = 0.The passage presents this as equivalent to the preceding derivative condition.Source: §B.2 · p. 20
• The unique maximum of f(T) on 0 ≤ T ≤ 1 occurs at the value identified in the passage.The passage gives the maximizer as T = 2 − … .Source: §B.2 · p. 20