Motivation
A delivery route must visit every location and return to its start. Finding a minimum-cost route can be difficult, but an approximation algorithm can produce a route with a proven cost relative to the unknown optimum. For metric distances, a minimum spanning tree gives a useful lower bound, and a walk around that tree gives a tour whose cost is at most twice the optimum.
The triangle inequality is what allows repeated visits to be removed without increasing cost. We also examine how matching the odd-degree tree vertices improves the argument to a factor of , assuming an exact minimum-weight perfect-matching algorithm as a separate computational ingredient.
Definitions and conventions
Definition 4.4.1
(Metric instance)
Let be a finite set of vertices. For every ordered pair , let , with , , and . Distinct vertices may have distance zero. The resulting complete undirected weighted graph is metric in the sense needed here.
Definition 4.4.2
(Tour and optimum)
A tour is a closed walk that visits every vertex exactly once before returning to its starting vertex. For , the tour traverses the single undirected edge twice. Let be the smallest tour cost. A walk may repeat vertices or edges; each traversal contributes its distance. If , the zero-cost stationary tour is optimal and can be returned separately.
Definition 4.4.3
(Spanning tree, multigraph and Euler tour)
A minimum spanning tree (MST) is a minimum-weight connected acyclic spanning subgraph. A multigraph may contain parallel copies of an edge; its degree counts each copy. An Euler tour of a connected even-degree multigraph traverses every edge copy exactly once and returns to its start. The standard Euler-tour construction follows unused edges and splices closed walks; it runs in time linear in the number of edge copies.
Theorems
Theorem 4.4.4
(Double-tree approximation)
A minimum spanning tree, with each edge doubled and its Euler tour shortcut to first visits, yields a tour of cost at most .
Theorem 4.4.5
(Odd-degree matching improvement)
Let be the odd-degree vertices of an MST. If an exact minimum-weight perfect matching on is added to the tree, an Euler tour of the resulting multigraph can be shortcut to a tour of cost at most .
A perfect matching on partitions its vertices into disjoint pairs and uses one edge per pair; for use the empty matching. The second theorem assumes such a minimum-weight matching can be computed. A polynomial-time general-graph weighted perfect-matching algorithm is a separate result, not proved in this chapter.
Proofs
A spanning-tree lower bound
Lemma 4.4.6
(Spanning-tree lower bound)
Give the complete graph on nonnegative edge weights, and let be a minimum spanning tree. Then .
Proof
(Delete one edge of an optimal tour)
Take an optimal tour. For , remove any one of its edges. The remaining edges form a spanning path and hence a spanning tree; nonnegative edge weights make its cost no greater than the tour cost. For , removing one of the two traversals leaves the single spanning edge, also with no greater cost. An MST is no more expensive than this tree, so
The argument does not need the triangle inequality. It uses completeness to ensure a tour exists and nonnegative weights to justify deleting an edge without increasing cost.
Double a tree and shortcut the walk
Proof
(Double the tree, then shortcut)
Double every edge of the MST . The resulting connected multigraph has even degree at every vertex. An Euler tour therefore exists and has cost exactly . It may visit vertices many times, so it is not yet a salesperson tour.
Start at the chosen vertex and list vertices in the order in which the Euler walk first visits them. Connect consecutive listed vertices directly, then connect the last one back to the start. Every vertex appears once before the return. Each direct edge replaces a consecutive portion of the original walk. Repeated application of the triangle inequality shows that the direct edge costs no more than that portion. These portions partition the walk, including the final return portion, so the shortcut tour costs at most .
For two vertices, shortcutting leaves the two opposite traversals of their edge, exactly the required closed tour. Zero-weight edges cause no problem; inequalities are non-strict. If , the proof gives a tour of cost zero. The multiplicative statement remains meaningful as an inequality, without dividing by zero.
Proof X-ray
The lower and upper bounds meet at the tree
The factor two comes from three separate moves, and each uses a different hypothesis. Deleting one edge of an optimal tour uses only nonnegative weights and gives . Doubling the tree uses no distances at all: it makes every degree even, so an Euler walk of cost exactly exists. Shortcutting is the only step that uses the triangle inequality, once for each stretch of the walk that it replaces by a direct edge. Chaining the three, the shortcut tour costs at most , and .
Matching odd-degree vertices
Proof
(Parity, alternating matchings and shortcutting)
A finite undirected graph has an even number of odd-degree vertices because its degree sum is twice the number of edges. Let be the odd-degree vertices of , and let be a minimum-weight perfect matching on . Adding to changes the parity of exactly the vertices in , making every degree even. The result is still connected, so it has an Euler tour of cost .
We show . Traverse an optimal tour and keep only vertices of , shortcutting between consecutive retained vertices. The triangle inequality makes the resulting closed walk on no more expensive than the original tour. When , its cyclic edges split alternately into two perfect matchings. Their combined cost is the walk cost, so the cheaper matching costs at most half of it. The minimum matching is no more expensive than that one.
When , the shortcut closed walk traverses the edge between the two odd vertices in both directions. Treating those traversals as two edge copies gives two one-edge perfect matchings, each of that edge's cost; the same half-cost conclusion holds. When , is empty and its cost is zero. Thus in every case .
The Euler walk costs at most . Shortcutting it by first visits cannot increase its cost, so the final tour satisfies the second theorem. This proof gives a cost guarantee even if several MSTs, minimum matchings or optimal tours tie.
Proof X-ray
Where the matching bound comes from
The handshake parity of degrees is used once: is even, so a perfect matching exists and adding it makes every degree even. The triangle inequality is used twice, to shortcut the optimal tour down to and to shortcut the final Euler walk. The key move is that a closed walk on an even number of vertices splits into two matchings, so the cheaper has cost at most half of the walk. Minimality of is what lets it be compared with that cheaper one.
Algorithmic cost and scope
The complete graph has edges. An MST can be found in polynomial time; for example, a suitable array implementation of Prim's algorithm takes comparisons on a dense graph. Doubling its edges, finding the Euler tour and shortcutting take time or less with a straightforward representation. Thus the factor-two algorithm is polynomial in the explicit distance-matrix input size.
For the factor- algorithm, add the cost of an exact minimum-weight perfect-matching routine on at most odd vertices. Such a routine is known to be polynomial for general weighted graphs under appropriate exact-arithmetic assumptions, but this chapter does not prove that algorithm or its bit complexity. The approximation proof is conditional on obtaining a minimum matching, not on a greedy pairing that merely looks short.
If distances are rational or integer values, the count of arithmetic operations is not automatically a bit-time bound. Implementations must represent sums and compare weights accurately. The theorem concerns exact distances satisfying all the metric assumptions; floating-point rounding may require a separate analysis.
Worked examples
Worked example 4.4.7
(Three equally spaced vertices)
Let every distinct pair have distance one. An MST has two edges and cost two. Doubling it gives an Euler walk of cost four. Shortcutting repeated vertices yields a three-edge tour of cost three, which is optimal. The factor-two guarantee permits cost up to six; it is an upper bound, not a prediction that the algorithm always pays twice the optimum.
Concept lensAlgorithmic
The double-tree tour is a preorder traversal
Root the MST and take the depth-first walk that goes down each edge once and back up once; this is an Euler tour of the doubled tree. The vertices in order of first visit are exactly the preorder of the rooted tree. So the algorithm is: build an MST, list its vertices in preorder, and return to the root.
Worked example 4.4.8
(A four-vertex line metric)
Place vertices at coordinates on a line, with distance equal to absolute difference. The path through consecutive coordinates is an MST of cost three. The tour costs ; the double-tree walk can shortcut to this tour. The odd-degree set of the path consists of its endpoints, and their matching costs three, so the matching construction also yields a walk of cost six.
Worked example 4.4.9
(The two-vertex boundary)
For two vertices at distance , the MST costs and the required closed tour costs . Both tree vertices have odd degree, and their perfect matching is the one edge of cost . Adding it as a second edge copy gives an Euler tour of cost , exactly optimal.
Worked example 4.4.10
(Shortcutting needs the triangle inequality)
Suppose three pairwise edge costs are , and . A doubled path costs four. Shortcutting to costs twelve, so shortcutting increased cost. These values violate the triangle inequality because ; the metric approximation proof does not apply.
Counterexample mode
A walk is not automatically a tour
Claim: the Euler walk of the doubled MST is already a salesperson tour. Take four vertices with every distance equal to ; this is a metric. The star with center and leaves is an MST of cost . Doubling it gives the Euler walk of cost , which visits four times, so it is not a tour. Shortcutting to first visits gives of cost . The corrected statement is that the walk becomes a tour only after shortcutting, and the triangle inequality, here for each replaced stretch, is what keeps the shortcut tour no more expensive than the walk.
Common mistakes
Common mistake
(A spanning tree is not a tour)
The MST is a lower bound on the optimal tour, but it is not itself a tour: its leaves have odd degree and a tree does not generally supply a closed route visiting each vertex once. Doubling produces a closed walk, and shortcutting produces the required tour. Each transformation has its own proof obligation.
Common mistake
(A greedy pairing is not the minimum matching)
The odd-degree matching must pair all odd vertices. Pairing only nearby neighbors greedily can produce a perfect matching more expensive than the minimum, so the proof cannot be applied to an arbitrary pairing. An approximation algorithm for matching would require a correspondingly adjusted analysis.
Common mistake
(The optimum is a benchmark, not an input)
Finally, the guarantee compares the algorithm's result to the optimum on the same instance. The algorithm does not need to know to run. The optimal tour appears only in the proof as a benchmark used to bound the tree and matching costs.
Summary
Removing a tour edge gives the MST lower bound. Doubling the tree makes its degrees even, and shortcutting an Euler walk in a metric yields a tour costing at most twice optimum. Matching the tree's odd-degree vertices costs at most half an optimal tour and improves the bound to , conditional on computing a minimum perfect matching. The triangle inequality, parity and nonnegative costs each have a distinct role.
Exercises
Quick check
(Explain why doubling every edge of a tree makes every vertex degree even.)
Count the edge copies at one vertex.
Solution · Answer
Every incident edge contributes two edge copies after doubling, so every original degree is multiplied by two and becomes even. The graph remains connected.
Quick check
(For a two-vertex metric with distance , compute the MST cost, optimal tour cost and matching-augmented Euler-walk cost.)
Use the two-vertex boundary example.
Solution · Answer
The MST has the single edge of cost seven. The closed tour traverses that edge twice, costing fourteen. Both vertices have odd tree degree; the matching adds one edge copy of cost seven, giving an Euler walk of cost fourteen.
Quick check
(Why does a tour's cost bound the MST cost from above? Treat the role of nonnegative weights explicitly.)
Which edge do you delete?
Solution · Answer
Removing one edge from a tour on at least three vertices leaves a spanning path, hence a spanning tree. Since the removed edge has nonnegative weight, the remaining tree costs at most the tour. The MST costs no more than that tree. For two vertices remove one of the two edge traversals.
Quick check
(Let contain four vertices listed in cyclic order along a shortcut optimal tour, with edge costs . Give the two alternating matchings and bound the minimum matching cost.)
Split the cycle into alternate edges.
Solution · Answer
The alternating edge sets have costs and . Both are perfect matchings on the four listed vertices, so the minimum matching costs at most , and in particular at most half of the shortcut tour cost .