DHP/DHC/UHC/UHP ≤p each other

The construction

The economical argument. Naively one needs a reduction for every ordered pair, i.e. $4\cdot3=12$ of them. But $\le_p$ is transitive, so a cycle of four suffices:

$DHP\ \le_p\ DHC\ \le_p\ UHC\ \le_p\ UHP\ \le_p\ DHP .$

Every node reaches every other by walking around the cycle, and any such walk composes at most three reductions — and a composition of polynomials is a polynomial. Twelve drops to four.

The composition, justified in full. If $f$ computes $A\le_p B$ in time $p(n)$ and $g$ computes $B\le_p C$ in time $q(n)$ , then $|f(x)|\le p(|x|)$ — in time $p(|x|)$ one cannot write more than $p(|x|)$ symbols — so computing $g(f(x))$ costs $p(|x|)+q(p(|x|))$ , a polynomial. And $x\in A\iff f(x)\in B\iff g(f(x))\in C$ .

The starting point. The course states without proof that $\mathrm{3SAT}\le_p DHP$ , so $DHP$ is NP-hard; the lecturer said explicitly that this reduction is "cute but very, very tedious" and is therefore skipped — the result must be known, the proof need not be. Once $DHP$ is hard, the cycle carries hardness to the other three.

All four are in NP. The certificate is an ordering of the vertices (a permutation of $V$ ), of length $O(|V|\log|V|)$ . The verifier checks that consecutive vertices are joined by an edge (in a directed graph, an edge in the right direction), and for a cycle also checks the closing edge from last to first. Polynomial time. So all four are NP-complete.

Visualization

Known-hard Asource instance x

f(x)total polynomial compiler

Target B solverhypothetical fast algorithm

The solver's yes/no answer decides A

Correctness — both directions

DHP/DHC/UHC/UHP ∈ ⟹ each other ∈

The link $DHC\le_p UHC$ is proved in full in its own entry. The other three links were assigned as homework and are not written out in the course sources.

The general shape of each is the same: turn a path problem into a cycle problem by adding a vertex (or pair of vertices) that forces the closure, and turn an undirected graph into a directed one by replacing each edge with a pair of opposite arcs. In each case the forward direction is proved by exhibiting the corresponding path or cycle explicitly.

each other ∈ ⟹ DHP/DHC/UHC/UHP ∈

Again, the $UHC$ link is proved in full in its own entry; for the other links the proof follows the same pattern — one shows the added structure (the forcing vertex, the pair of opposite arcs) constrains the target-side solutions enough that a source-side solution can be read off.

Why the cycle suffices — the full argument. Let $X,Y$ be two of the four problems. In a four-node cycle, the directed distance from $X$ to $Y$ is at most $3$ . Compose the reductions along that path; by the composition computation above, composing at most three polynomial reductions yields a polynomial reduction. So $X\le_p Y$ for every pair, i.e. all four are equivalent.

Cost of the reduction

Timepolynomial (composition of ≤ 3 links)

Spacepolynomial

Output sizepolynomial in the input

Output length is what makes the composition legal: a machine running $t$ steps writes an output of length $O(t)$ at most, so the intermediate length is polynomially bounded and a composition of polynomials is a polynomial. A reduction that inflates its input exponentially — correct though it may be — is useless in such a chain.

What it buys

All four Hamiltonian problems are NP-complete. A warning raised in class: the algorithms course gave a polynomial algorithm via topological sort — true, but only for a directed acyclic graph, a very specific case, and no contradiction with the general problem's hardness.

Pitfalls

Transitivity is what saves the work, not the problems' "similarity". One cannot say "the problems are similar, hence equivalent"; an explicit cycle of reductions is required, together with an explanation of why it suffices.

The chain

Rests on

DHC ≤p UHC

Used later by

UHC ≤p TSP

Where this was read from

Lesson 12משפט 7: ארבע הבעיות ההמילטוניות
Lesson 12תרגיל 4 (מהכיתה, [01:16:34]): כמה רדוקציות נדרשות לארבע הבעיות ההמילטוניות?
2026"Prove $DHP,DHC,UHC,UHP$ are polynomially equivalent… explain why this suffices."
2023 '2 מועד 1"Recall the reduction $SAT\le_P dHP$ shown in class" — counting the output for a formula with 100 clauses.

Three of the cycle's four links are written in no source in the corpus — they were assigned as homework. This entry records the structure of the argument and the one link that was written out; the constructions for $DHP\le_p DHC$ , $UHC\le_p UHP$ , and $UHP\le_p DHP$ are not documented here, so as not to attribute to the course a construction it never gave.
The reduction $\mathrm{3SAT}\le_p DHP$ , the family's starting point, was stated in the course explicitly without proof. The 2023 paper refers to it as "the reduction we showed in class", so in earlier years it was given.