DHC ≤p UHC | Complexity Atlas

The construction

Given a directed graph $G=(V,E)$ , build an undirected $G'=(V',E')$ :

$V'=\{v_{in}:v\in V\}\cup\{v_{mid}:v\in V\}\cup\{v_{out}:v\in V\},$ $E'=\{v_{in}v_{mid}:v\in V\}\ \cup\ \{v_{mid}v_{out}:v\in V\}\ \cup\ \{u_{out}v_{in}:uv\in E\}.$

So each vertex becomes a path of length two $v_{in}-v_{mid}-v_{out}$ , and each directed edge $u\to v$ becomes an undirected edge from the out of $u$ to the in of $v$ .

What encodes the orientation. The vertex $v_{mid}$ has degree exactly $2$ — its only neighbours are $v_{in}$ and $v_{out}$ . A Hamiltonian cycle must visit every vertex, and at a degree- $2$ vertex it must use both incident edges. So every Hamiltonian cycle of $G'$ traverses each triple as $v_{in}\to v_{mid}\to v_{out}$ or its reverse — and since the cycle is a single closed walk, that choice is uniform across all triples. That is precisely the orientation lost in passing to an undirected graph.

Visualization

Correctness — both directions

DHC ∈ ⟹ UHC ∈

Suppose $G\in DHC$ ; $G$ has a directed Hamiltonian cycle $v^{(1)}\to v^{(2)}\to\dots\to v^{(n)}\to v^{(1)}$ .

Build in $G'$ the cycle $v^{(1)}_{in}\to v^{(1)}_{mid}\to v^{(1)}_{out}\to v^{(2)}_{in}\to v^{(2)}_{mid}\to v^{(2)}_{out}\to\dots\to v^{(n)}_{out}\to v^{(1)}_{in}.$

Every edge exists: the edges $v_{in}v_{mid}$ and $v_{mid}v_{out}$ exist for every $v$ by construction; and $v^{(t)}_{out}v^{(t+1)}_{in}$ exists because $v^{(t)}v^{(t+1)}$ is a directed edge of $G$ (it is a cycle edge).

It is Hamiltonian: it visits each of $v_{in},v_{mid},v_{out}$ for every $v\in V$ exactly once, since the original cycle visits each $v$ exactly once. So it covers all $|V'|=3|V|$ vertices. Hence $G'\in UHC$ .

UHC ∈ ⟹ DHC ∈

Suppose $G'\in UHC$ , with Hamiltonian cycle $C'$ .

Step 1 — the triples are traversed consecutively. Let $v\in V$ . The vertex $v_{mid}$ has degree $2$ in $G'$ : its only neighbours are $v_{in}$ and $v_{out}$ (the construction gives it no other edge). A Hamiltonian cycle passes through $v_{mid}$ using exactly two incident edges, and since only two exist it uses both. So $C'$ contains the segment $v_{in}-v_{mid}-v_{out}$ (in one of the two directions).

Step 2 — the direction is uniform. Fix a direction of travel along $C'$ . By Step 1, in each triple $C'$ enters at $v_{in}$ and leaves at $v_{out}$ , or the reverse. Without loss of generality (reversing the direction of travel if needed) some triple is entered at $v_{in}$ . We show all are: the edge following $v_{out}$ in $C'$ is not internal to the triple, so it has the form $v_{out}u_{in}$ — the only edges leaving an $out$ vertex go to $in$ vertices. So the next triple is likewise entered at $u_{in}$ . By induction along the cycle, every triple is traversed as $in\to mid\to out$ .

Step 3 — reading off the directed cycle. Let $v^{(1)},v^{(2)},\dots,v^{(n)}$ be the order of the triples along $C'$ . By Step 2, between the triple of $v^{(t)}$ and that of $v^{(t+1)}$ , $C'$ uses the edge $v^{(t)}_{out}v^{(t+1)}_{in}$ . Edges of this kind exist only when $v^{(t)}v^{(t+1)}\in E$ — that is how $E'$ was defined. So $v^{(t)}\to v^{(t+1)}$ is a directed edge of $G$ for every $t$ , and so is $v^{(n)}\to v^{(1)}$ (the closing edge).

Since $C'$ is Hamiltonian in $G'$ , each triple occurs exactly once, so $v^{(1)},\dots,v^{(n)}$ are all vertices of $V$ , each once. Hence $v^{(1)}\to\dots\to v^{(n)}\to v^{(1)}$ is a directed Hamiltonian cycle in $G$ , i.e. $G\in DHC$ .

Cost of the reduction

TimeO(|V| + |E|)

SpaceO(|V| + |E|)

Output size3|V| vertices, 2|V| + |E| edges

One pass over the vertices (three vertices and two edges each) and one over the edges (one edge each). Linear in the input size.

What it buys

One link of the cycle $DHP\le_p DHC\le_p UHC\le_p UHP\le_p DHP$ , showing the four Hamiltonian problems are polynomially equivalent, so if one is NP-hard, all are.

Pitfalls

$v_{mid}$ is not decoration. Without it, $v_{in}$ and $v_{out}$ would share a single edge and the cycle could cross a triple without any order being forced. The degree- $2$ property of $v_{mid}$ is the entire forcing mechanism.
Uniformity of direction needs proof. "Each triple is traversed in some direction" is not enough — one needs the argument that an edge leaving an $out$ vertex always arrives at an $in$ vertex, so the direction propagates around the whole cycle. Without Step 2 there is no way to read a directed cycle off the undirected one.

The chain

Used later by

DHP/DHC/UHC/UHP ≤p each other

Where this was read from

2026"Prove the algorithm is a polynomial-time reduction from $DHC$ to $UHC$ " — the construction is given in full in the question.
2026The same construction, phrased as set definitions of $V'$ and $E'$ .

Lesson 12 assigns all four Hamiltonian reductions as homework and writes none of them; what the lesson does write is only the transitivity argument (why four reductions suffice instead of twelve). The construction above is copied from the phrasing the 2026 papers give it.