Analyze the Metric TSP Double-Tree Algorithm

Combine an MST lower bound, Euler traversal, and metric shortcutting for a factor-two tour.

Problem

For a complete graph with nonnegative symmetric costs satisfying the triangle inequality, analyze: compute an MST, double every tree edge, take an Euler tour, and shortcut repeated vertices. Prove a Hamiltonian tour of cost at most $2\,\mathrm{OPT}$ and give polynomial runtime.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

Deleting one edge from an optimal tour leaves a spanning tree.

Hint 2

Doubling makes every tree degree even.

Hint 3

Triangle inequality proves that skipping visited vertices cannot increase cost.

Full solution

Let $T$ be a minimum spanning tree. Remove any edge from an optimal Hamiltonian tour; the remaining edges form a spanning path and therefore a spanning tree. By minimality,

After doubling every edge of $T$, the resulting connected multigraph has even degree at every vertex, so it has an Euler circuit. Its cost is exactly $2w(T)$.

Traverse that Euler circuit and record each vertex only at its first occurrence, finally returning to the start. This produces a Hamiltonian cycle because every tree vertex appears in the Euler circuit. Whenever the Euler walk contains a segment from $u$ through already visited vertices to the next new vertex $v$, replace the segment by edge $(u,v)$. Completeness ensures the shortcut edge exists. Repeated application of the triangle inequality shows its cost is no greater than the skipped path. Therefore

Every stage is polynomial. A dense implementation computes an MST in $O(n^2)$ or $O(n^2\log n)$ time, forms $2(n-1)$ multiedges, finds an Euler tour in linear time in that multigraph, and shortcuts using a visited array. Cost arithmetic is polynomial in the binary lengths of edge weights. The output visits every vertex once and returns to its start.

The assumptions are all used. Without triangle inequality, one shortcut may be arbitrarily more expensive than the path it replaces. Without completeness, the shortcut edge may not exist. Negative costs undermine standard metric interpretation and lower-bound reasoning, although ordinary metrics are nonnegative. Symmetry is for the undirected version; directed metric TSP requires different methods.

The analysis gives approximation ratio two, often stated as “at most twice optimum.” It does not show equality, and it does not claim the MST itself is a tour. Doubling is what supplies even degrees; shortcutting is what turns the Euler walk, which repeats vertices, into a legal TSP tour.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Claiming an MST is itself a Hamiltonian tour.
• Shortcutting without citing completeness and triangle inequality.
• Reversing the lower bound $w(T)\le\mathrm{OPT}$.

Sources and verification

• Papadimitriou, ch. 13 (metric TSP approximation)
• Corpus coverage note: No direct merged-summary coverage; pp. 79-80 contain only a related Steiner-tree pattern.
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.

Open in the visualization gallery: Metric TSP double-tree 2-approximation