UHC ≤p TSP | Complexity Atlas

The construction

Algorithm $R''$ . On input $G=(V,E)$ — a simple undirected graph:

Let $\hat G=(V,\hat E)$ be the complete graph on $V$ .
Define $w:\hat E\to[0,\infty)$ by $w(e)=\begin{cases}1 & e\in E\\ 2 & e\notin E\end{cases}$
Return $\left(\hat G,\;w,\;|V|\right)$ .

Why from $UHC$ . One could start from a Hamiltonian path — there are reductions between all versions — but $TSP$ asks about a cycle in an undirected graph, so $UHC$ is the nearest problem. The same principle recurs: start from the closest problem.

On step 1. Once $V$ is fixed there is a unique complete graph on it; no choice is involved. In practice step 1 means "write down all the edges", including those absent from $G$ .

Visualization

Original edge of G — cost 1

Correctness — both directions

UHC ∈ ⟹ TSP ∈

Suppose $G\in UHC$ ; then $G$ has a Hamiltonian cycle $C$ . Since $E\subseteq\hat E$ , that same $C$ is a cycle in $\hat G$ , and Hamiltonian there too — the vertex set did not change, only edges were added.

A Hamiltonian cycle on $|V|$ vertices has exactly $|V|$ edges, each of them an edge of $E$ and therefore of weight $1$ . So $w(C)=|V|\cdot1=|V|\le|V| ,$ hence $(\hat G,w,|V|)\in TSP$ .

TSP ∈ ⟹ UHC ∈

The lecture deliberately gave two versions of this direction — to show there is nothing sacred about proving "in $\Rightarrow$ in" versus "out $\Rightarrow$ out". Both are correct.

Version A (by contradiction). Suppose $G\notin UHC$ , and let $C$ be any Hamiltonian cycle in $\hat G$ (one exists, as $\hat G$ is complete). $C$ has exactly $|V|$ edges, each of weight at least $1$ . Moreover $C$ contains an edge outside $E$ — otherwise all its edges would lie in $E$ and $C$ would be a Hamiltonian cycle of $G$ , contradicting the hypothesis. That edge has weight $2$ . So $w(C)\ge(|V|-1)\cdot1+2=|V|+1>|V| .$ This holds for every Hamiltonian cycle in $\hat G$ , so none has weight $\le|V|$ , i.e. $(\hat G,w,|V|)\notin TSP$ .

Version B (direct, and two lines shorter). Suppose $(\hat G,w,|V|)\in TSP$ ; then some Hamiltonian cycle $C$ in $\hat G$ has $w(C)\le|V|$ . Since every edge weighs at least $1$ and $C$ has exactly $|V|$ edges, $w(C)\ge|V|$ . The two inequalities give $w(C)=|V|$ exactly. Now $w(C)$ is a sum of $|V|$ terms each $\ge1$ totalling exactly $|V|$ ; were any term $>1$ the sum would exceed $|V|$ . So each of the $|V|$ edges weighs exactly $1$ , and by the definition of $w$ each lies in $E$ . Hence $C$ is a Hamiltonian cycle of $G$ , i.e. $G\in UHC$ .

Cost of the reduction

TimeO(|V|²)

SpaceO(|V|²)

Output sizeO(|V|²)

This analysis needs care. The work is a pass over all of $\hat E$ , writing a weight for each — $\Theta(|\hat E|)$ . The temptation is to say "that's linear" — but linear in what? It is linear in the size of the new graph, whereas running time must be bounded in the size of the input.

The difficulty: we do not know how many edges $G$ had; conceivably very few, even none. So $|\hat E|$ cannot be bounded via $|E|$ . What is certain is $|\hat E|=\binom{|V|}{2}\le|V|^2$ , and the vertex count is unchanged by the reduction and bounded by the input size. So the running time is $O(|V|^2)=O(|x|^2)$ — quadratic in the input size.

What it buys

$TSP$ is NP-complete. And a bonus: weights valued in $\{1,2\}$ satisfy the triangle inequality, since for all $u,x,v$ we have $w(u,v)\le2=1+1\le w(u,x)+w(x,v)$ . So the very same reduction shows $TSP$ stays NP-hard in its metric version — the version that does admit an approximation algorithm (double tree, ratio $2$ ).

Pitfalls

Why $\{1,2\}$ and not $\{0,1\}$ . The first natural construction proposed in class was weight $0$ on original edges and $1$ on new ones, with $K=0$ . That construction is entirely correct and it works — but it forfeits the bonus: with weights $0$ and $1$ the triangle inequality fails ( $1\not\le0+0$ ), so it proves nothing about the metric version.
"Linear" in output size is not "linear" in input size. This is the point the lecturer dwelt on: $|\hat E|$ cannot be bounded via $|E|$ , since $G$ might have been nearly edgeless. The bound must go through $|V|$ .

The chain

Rests on

DHP/DHC/UHC/UHP ≤p each other

Used later by

UHC ≤p TSP-OPT

Where this was read from

Lesson 12משפט 8: $UHC \le_p TSP$ , ולכן $TSP$ היא NP-hard
Guided exercisehamiltonian-cycle-to-tsp
2026 '1 מועד 1An algorithm returning a complete weighted graph with $x$ on existing edges and $y$ on missing ones — which claim about the reduction holds.