Four Costs to Compare
For a weighted complete graph, a Hamiltonian cycle is a tour: it visits every vertex exactly once and returns to its starting vertex. Its cost is the sum of its edge weights. A heuristic constructs a tour, so its cost is an upper bound on the optimum tour cost. A lower-bound method instead gives a number no greater than the optimum. Comparing both kinds of numbers on the same graph helps distinguish a good tour from a strong bound.
Throughout, graphs are finite, simple, and complete, and edge weights are positive, symmetric, and satisfy the triangle inequality. Thus \(w(uv)=w(vu)\), and \(w(uv)\leq w(ux)+w(xv)\) for all vertices \(u,v,x\). This is the metric TSP setting needed for Christofides’ algorithm and for shortcutting a walk without increasing its cost.
The nearest-neighbor heuristic starts at a chosen vertex and repeatedly goes to a least-weight edge joining the current vertex to an unvisited vertex. After all vertices have been visited, it returns to its start. When there is a tie, the chosen tie-break must be stated: different choices can produce different tours.
Christofides’ algorithm first finds a minimum spanning tree \(T\). It then finds a minimum-weight perfect matching on the vertices of odd degree in \(T\), adds those matching edges to \(T\), takes an Euler circuit in the resulting connected multigraph, and shortcuts repeated vertices to obtain a tour. A perfect matching pairs every vertex in the specified set exactly once. The odd-degree set has even size because the sum of all degrees is twice the number of tree edges.
Why the Two Bounds Are Valid
Proof. Let \(H\) be any Hamiltonian cycle. Removing one edge of \(H\) leaves a spanning path: all vertices remain connected, and the remaining edges contain no cycle. This path is a spanning tree. Its cost is the cost of \(H\) minus the positive weight of the removed edge, so it is less than the cost of \(H\). The minimum spanning tree costs no more than this particular spanning tree, and hence no more than \(H\).
Now fix a root \(r\). Remove \(r\) and its two incident tour edges from \(H\). The remaining edges form a spanning path on \(V\setminus\{r\}\), which is a spanning tree on that vertex set. Restoring the two removed edges gives a rooted one-tree of exactly the same cost as \(H\). The minimum rooted one-tree costs no more than this candidate. Taking \(H\) to be an optimal tour proves both lower bounds. \(\square\)
Here is why the Christofides construction produces a tour. Each odd-degree vertex of \(T\) gains one matching edge, so its degree becomes even; each other vertex keeps its even degree. The multigraph is connected because it contains \(T\). A connected multigraph in which every degree is even has an Euler circuit: follow unused edges until returning to the starting vertex, and, if unused edges remain, splice in another closed trail from a vertex already on the circuit. Even degrees ensure that a trail cannot get stuck at a different vertex; finiteness ensures the process ends after all edges are used. The Euler circuit visits every vertex, possibly more than once. Delete repeated visits by replacing each intervening section from \(u\) to \(v\) with the edge \(uv\). Repeated use of the triangle inequality shows that such shortcuts do not increase cost. Since the graph is complete, each shortcut edge exists. The result is a Hamiltonian cycle. This argument verifies that the procedure gives a tour; it does not assert that the tour is optimal.
Worked Comparisons
Worked Example: A Square Metric
Let \(V=\{a,b,c,d\}\), with all six edges of the complete graph present. Set \(w(ab)=1\), \(w(bc)=1\), \(w(cd)=1\), \(w(da)=1\), \(w(ac)=2\), and \(w(bd)=2\). These weights are metric: each weight is at most the sum along either two-edge route through a third vertex. For instance, \(w(ac)=2\leq w(ab)+w(bc)=1+1=2\), and all other checks have the same form.
A minimum spanning tree is \(\{ab,bc,cd\}\), of cost \(1+1+1=3\). To see it is minimum, the three smallest edge weights are \(1,1,1\), so any three-edge spanning tree costs at least \(3\); these three edges do form a tree.
For a rooted one-tree with root \(a\), the nonroot vertices \(b,c,d\) have a minimum spanning tree \(\{bc,cd\}\), of cost \(1+1=2\). The two cheapest distinct edges from \(a\) are \(ab\) and \(ad\), of total cost \(1+1=2\). Thus this rooted one-tree costs \(2+2=4\).
Run nearest neighbor from \(a\), breaking ties by choosing \(b\) before \(d\). From \(a\), the least edge to an unvisited vertex is \(ab\), of weight \(1\). From \(b\), choose \(c\), also of weight \(1\), rather than \(d\), of weight \(2\). From \(c\), the only unvisited vertex is \(d\), reached at cost \(1\). The return edge \(da\) costs \(1\). The tour \(a,b,c,d,a\) therefore costs \(1+1+1+1=4\).
For Christofides’ algorithm, use the minimum spanning tree \(\{ab,bc,cd\}\). Its odd-degree vertices are \(a\) and \(d\), so the matching consists of \(ad\), of cost \(1\). The resulting multigraph has two copies of \(ad\) and one copy each of \(ab,bc,cd\). An Euler circuit is \(a,b,c,d,a\), with cost \(1+1+1+1=4\), and no shortcut is needed.
Check: The spanning-tree bound is \(3\), the rooted one-tree bound is \(4\), and both constructed tours cost \(4\). The one-tree bound equals the displayed tour cost; by the lower-bound theorem, that tour is optimal.
Worked Example: A Rooted One-Tree Can Leave a Gap
Let \(V=\{a,b,c,d\}\), with all six edges present, and weights \(w(ab)=1\), \(w(bc)=1\), \(w(bd)=1\), \(w(ac)=2\), \(w(ad)=2\), and \(w(cd)=2\). These are metric weights: every weight \(1\) satisfies the triangle inequalities because weights are positive, and every weight \(2\) has a two-edge route of cost \(1+1=2\), such as \(a\) to \(c\) through \(b\).
The edges \(ab,bc,bd\) form a spanning tree of cost \(1+1+1=3\). No spanning tree can cost less: it has three edges, and every edge has weight at least \(1\), so its cost is at least \(1+1+1=3\).
Take \(a\) as root. On \(\{b,c,d\}\), the edges \(bc\) and \(bd\) form a spanning tree of cost \(1+1=2\); the third edge \(cd\) has weight \(2\), so no pair of edges can cost less than \(2\). The two cheapest distinct edges from \(a\) are \(ab\), of weight \(1\), and either \(ac\) or \(ad\), of weight \(2\). The minimum rooted one-tree cost is therefore \(2+1+2=5\).
Start nearest neighbor at \(a\), and choose \(b\) in the tie between \(b\) and \(c,d\) at weight \(1\). From \(b\), choose \(c\) in the tie between \(c\) and \(d\), both at weight \(1\). Then go from \(c\) to \(d\) at weight \(2\), and return from \(d\) to \(a\) at weight \(2\). The tour \(a,b,c,d,a\) costs \(1+1+2+2=6\).
For Christofides, use the star-shaped minimum spanning tree \(\{ab,bc,bd\}\). All four vertices have odd degree: \(b\) has degree \(3\), and \(a,c,d\) each have degree \(1\). The three possible perfect matchings have costs \(w(ab)+w(cd)=1+2=3\), \(w(ac)+w(bd)=2+1=3\), and \(w(ad)+w(bc)=2+1=3\). Choose \(\{ab,cd\}\). An Euler circuit in the resulting multigraph is \(a,b,c,d,b,a\), of cost \(1+1+2+1+1=6\). Shortcut the repeated \(b\) to obtain \(a,b,c,d,a\), whose cost is \(1+1+2+2=6\).
Check: The tour of cost \(6\) is optimal: the rooted one-tree lower bound is \(5\), and, more decisively, every tour must use two edges incident with \(a\), whose total is at least \(1+2=3\), and must connect \(c\) and \(d\) through the other two edges of its cycle. Directly checking the three undirected Hamiltonian cycles gives costs \(6\), \(6\), and \(6\): their edge sets are \(\{ab,bc,cd,da\}\), \(\{ab,bd,dc,ca\}\), and \(\{ac,cb,bd,da\}\). Thus the optimum is \(6\), while the rooted one-tree bound \(5\) is not exact.
Worked Example: The Same Bounds on a Five-Cycle Metric
Let \(V=\{1,2,3,4,5\}\), with all ten edges present. Give weight \(1\) to \(12,23,34,45,51\), and weight \(2\) to \(13,14,24,25,35\). These weights are the shortest-path distances around the 5-cycle, so they satisfy the triangle inequality. For example, \(w(13)=2\leq w(12)+w(23)=1+1=2\).
The path with edges \(12,23,34,45\) is a spanning tree of cost \(1+1+1+1=4\). Every spanning tree has four edges, each of weight at least \(1\), so \(4\) is also a lower bound on the cost of any spanning tree.
With root \(1\), the path \(23,34,45\) spans the other four vertices and costs \(1+1+1=3\). The two cheapest root edges are \(12\) and \(15\), both of weight \(1\). This rooted one-tree costs \(3+1+1=5\).
For nearest neighbor from \(1\), choose \(2\) rather than \(5\) in the tie at weight \(1\). Then choose \(3\) from \(2\), \(4\) from \(3\), and \(5\) from \(4\), each at weight \(1\). Returning from \(5\) to \(1\) costs \(1\). The resulting tour costs \(1+1+1+1+1=5\).
In Christofides’ algorithm, take the same minimum spanning path. Its odd-degree vertices are \(1\) and \(5\), so the minimum matching is the single edge \(15\), of weight \(1\). The Euler circuit is the path followed by \(51\), and its cost is \(1+1+1+1+1=5\). It already visits each vertex once before returning, so shortcutting changes nothing.
Check: The rooted one-tree bound is \(5\), and the displayed tour costs \(5\). The lower-bound theorem therefore certifies that the tour is optimal. The spanning-tree bound \(4\) is valid but weaker on this instance.
Reading the Comparison Correctly
These examples illustrate several distinctions. A spanning-tree cost is a lower bound, not a tour cost: a tree does not include a return edge or have degree \(2\) at every vertex. A rooted one-tree includes two root edges, but its other vertices can still have degrees different from \(2\); it too need not be a tour. In the second example its cost \(5\) is strictly below the optimum \(6\).
Nearest neighbor and Christofides both produce tours, so their costs are upper bounds on the optimum. In the examples above, ties were specified because a different tie-break can change the nearest-neighbor output. Christofides also depends on the chosen minimum spanning tree and minimum matching when there are ties; the algorithm must be traced using the particular choices made.
For a new instance, record the quantities separately: the minimum spanning-tree cost, the rooted one-tree cost for the selected root, and the costs of the two tours. Check that each constructed tour contains every vertex exactly once before returning, and add its edge weights directly. If a tour cost equals a valid lower bound, the tour is optimal. If the costs differ, the lower bound alone does not establish optimality; it only limits how low the optimum could be.
Check Your Understanding
For each question, state any tie-break you use and show the edge weights in every cost calculation.
- In the square metric example, use root \(b\) instead of \(a\). Find the minimum rooted one-tree cost.
- In the second example, find the cost of the tour with edge set \(\{ac,cb,bd,da\}\). Compare it with the two lower bounds.
- Explain why deleting one edge from a Hamiltonian cycle gives a spanning tree, but does not generally give a rooted one-tree.
- For the five-cycle metric, start nearest neighbor at vertex \(3\). Give a valid tie-break, trace the choices, and calculate the tour cost.
- Suppose a computed tour has cost \(U\) and a valid rooted one-tree has cost \(L\), with \(L=U\). What can be concluded about the tour, and why?