UHC ≤p TSP-OPT | Complexity Atlas

The construction

Background to the phrasing. There is no proven "hardness" in the NP world: we never proved an NP-hard problem cannot be solved efficiently, only that it is hard relative to the rest of $\mathrm{NP}$ . So — especially for optimization problems, for which NP-hardness is not formally defined (it is defined via reductions between languages) — the results one can state are conditional hardness results: "if X were possible, then $\mathrm{P}=\mathrm{NP}$ ".

The algorithm. Let $\alpha\ge1$ and suppose for contradiction an $\alpha$ -approximation $A$ exists. Build an algorithm taking an undirected $G=(V,E)$ :

Build the complete graph $\hat G=(V,\hat E)$ on the same vertex set, and for every $e\in\hat E$ set $w(e)=\begin{cases}1 & e\in E\\ \alpha|V|+1 & e\notin E\end{cases}$
Run $A$ on $(\hat G,w)$ .
If the returned value is $\le\alpha|V|$ — accept; otherwise — reject.

This is almost the construction of $UHC\le_p TSP$ , but there the weights were $1$ and $2$ , whereas here a "missing" edge weighs a huge amount. That hugeness is what buys the gap against $\alpha$ .

This object is not a mapping reduction. It is an algorithm calling another algorithm as a subroutine and interpreting the answer — the kind of "reduction" familiar from algorithms courses. Hence the phrasing "the algorithm decides $UHC$ ", not "there is a reduction".

Visualization

n = |V| = 5 · α = 2 · α|V|+1 = 11 · threshold αn = 10

Original edge, w = 1

Why a Hamiltonian cycle existsThe chord {2,4} closes the cycle 1→2→4→5→3→1, which visits every vertex exactly once using only edges of G.

Why none exists in the bowtieDeleting vertex 3 leaves the two components {1,2} and {4,5}. A Hamiltonian cycle would have to pass through 3 twice to visit both, which a cycle cannot do.

Correctness — both directions

UHC ∈ ⟹ TSP-OPT ∈

$G\in UHC$ . Then $G$ has a Hamiltonian cycle $C_0$ . It exists in $\hat G$ too (as $E\subseteq\hat E$ ), all its edges lying in $E$ and so weighing $1$ each. A Hamiltonian cycle has exactly $n=|V|$ edges, so $w(C_0)=n$ .

Moreover every Hamiltonian cycle consists of $n$ edges each weighing at least $1$ , so $\mathrm{OPT}(\hat G,w)\ge n$ ; with the above, $\mathrm{OPT}(\hat G,w)=n$ exactly.

Since $A$ is an $\alpha$ -approximation for a minimization problem, its output satisfies $w(A(\hat G,w))\;\le\;\alpha\cdot\mathrm{OPT}(\hat G,w)\;=\;\alpha n .$ So step 3 accepts — as required.

TSP-OPT ∈ ⟹ UHC ∈

$G\notin UHC$ . Then $G$ has no Hamiltonian cycle. Let $C$ be any Hamiltonian cycle in $\hat G$ (one exists, as $\hat G$ is complete). Since $C$ is not a Hamiltonian cycle of $G$ , it must contain an edge $e^*\notin E$ , so $w(e^*)=\alpha n+1$ . The other $n-1$ edges contribute at least $1$ each, so $w(C)\;\ge\;(\alpha n+1)+(n-1)\;=\;\alpha n+n\;>\;\alpha n .$ This holds for every Hamiltonian cycle of $\hat G$ , in particular the minimum one, so $\mathrm{OPT}(\hat G,w)>\alpha n$ .

The approximation algorithm returns a feasible solution, and a feasible solution cannot be cheaper than the optimum, so $w(A(\hat G,w))\ge\mathrm{OPT}(\hat G,w)>\alpha n$ as well. So step 3 rejects — as required.

Note that both sides of the inequality were used. The forward direction used the "interesting" side ( $\mathrm{ALG}\le\alpha\,\mathrm{OPT}$ ); the backward direction used the trivial side ( $\mathrm{ALG}\ge\mathrm{OPT}$ ), which follows from the output being feasible. Without the feasibility requirement the second direction would collapse.

Conclusion. The algorithm decides $UHC$ in polynomial time, so $UHC\in\mathrm{P}$ . But $UHC$ is NP-hard, so every $L\in\mathrm{NP}$ satisfies $L\le_p UHC\in\mathrm{P}$ , i.e. $\mathrm{NP}\subseteq\mathrm{P}$ ; with the trivial containment, $\mathrm{P}=\mathrm{NP}$ .

Cost of the reduction

TimeO(|V|²) plus one call to A

SpaceO(|V|²)

Output sizeO(|V|²) for the constructed instance

Step 1 costs $O(|V|^2)$ : the complete graph has $\binom{|V|}{2}$ edges, each needing a test and a weight. The weight $\alpha|V|+1$ takes $O(\log(\alpha|V|))$ bits — a large but short number, which is exactly the difference between "a big number" and "a number you cannot write down".

Step 2 is polynomial because an approximation algorithm is by definition a polynomial algorithm, and $|(\hat G,w)|\le O(|G|^2)$ with a polynomial of a polynomial being a polynomial. Step 3 is one comparison.

What it buys

General $TSP$ has no constant-factor approximation at all, unless $\mathrm{P}=\mathrm{NP}$ . The full equivalence: an approximation at some ratio exists $\iff\mathrm{P}=\mathrm{NP}$ — the converse being immediate, since if $\mathrm{P}=\mathrm{NP}$ the optimization version can be solved exactly by binary search on the objective value, i.e. approximated within factor $1$ .

Pitfalls

The weights violate the triangle inequality wholesale — an expensive edge between two vertices joined by a cheap path. So the theorem speaks about general $TSP$ only, and does not contradict the $2$ -approximation for the metric version. That is the central point: exactly where the barrier breaks once the triangle inequality is imposed.
If $\alpha$ is not an integer, $\alpha n+1$ is not either. One may work with rational weights (and then $\alpha$ must be rational for it to be writable in polynomial time), or use $\lceil\alpha n\rceil+1$ ; then $w(C)\ge\lceil\alpha n\rceil+1+(n-1)>\alpha n$ and the proof goes through word for word.

The chain

Rests on

UHC ≤p TSP

Where this was read from

Lesson 13משפט 4: לכל $\alpha \ge 1$ — אם ניתן לקרב את בעיית הסוכן הנוסע הכללית ביחס $\alpha$ , אז $\mathrm{P}=\mathrm{NP}$
Guided exercisemetric-tsp-approximation

Both technical remarks — handling non-integral $\alpha$ , and the explicit note that the triangle inequality is violated — are not stated in the lecture; they are completions written into the lesson file.