19 Long-Path Problem and Reduction to Hamiltonian Cycle, Solving Hamiltonian Cycle using DP, Long-Path via Randomized Coloring

Lecture from: 29.04.2025 | Video: Homelab

The Long-Path Problem (Decision Version)

Problem Definition

Given an undirected graph $G=(V,E)$ and a non-negative integer $B\in {\mathbb{N}}_0$, the Long-Path problem asks:

Does there exist a path in $G$ of length exactly $B$?

• A path is a sequence of vertices with no repetitions.
• A path of length $B$ contains $B+1$ distinct vertices.

Computational Complexity

The Long-Path problem is NP-complete. It is closely related to the Hamiltonian Path and Hamiltonian Cycle problems:

• Hamiltonian Path: Does $G$ contain a simple path that visits every vertex exactly once? ↳ Equivalent to Long-Path with $B=|V|-1$.

• Hamiltonian Cycle: Does $G$ contain a simple cycle that visits every vertex exactly once?

Since both Hamiltonian problems are NP-complete, and no polynomial-time algorithms are known for NP-complete problems (assuming $\text{P}\ne \text{NP}$), it is unlikely that Long-Path admits an efficient algorithm.

Reduction from Hamiltonian Cycle to Long-Path

To show that Long-Path is NP-complete, we reduce from the Hamiltonian Cycle problem, which is a known NP-complete problem.

Theorem

If Long-Path can be solved in time $t(N)$ for graphs with $N$ nodes, then the Hamiltonian Cycle problem can be solved in time

for graphs with $n$ nodes.

High-Level Idea

Given a graph $G$ with $n$ vertices, we construct a new graph $G^{\prime }$ such that:

This reduction takes polynomial time.

Construction of $G^{\prime }$

Let $G=(V,E)$ with $|V|=n$. Construct $G^{\prime }=(V^{\prime },E^{\prime })$ as follows:

1. Select an arbitrary vertex $v^{\ast }\in V$.
2. Remove $v^{\ast }$ from $G$ (i.e., work with $G-\{v^{\ast }\}$).
3. For each neighbor $w_i$ of $v^{\ast }$ in $G$:
   • Add a new vertex ${\hat{w}}_i$ to $G^{\prime }$,
   • Add the edge $(w_i,{\hat{w}}_i)$ to $G^{\prime }$.

So, $G^{\prime }$ contains:

• All original vertices except $v^{\ast }$: $V\setminus \{v^{\ast }\}$,
• One new vertex ${\hat{w}}_i$ for each neighbor $w_i$ of $v^{\ast }$,
• The same edges as $G$, minus those incident to $v^{\ast }$,
• New edges from each $w_i$ to its corresponding ${\hat{w}}_i$.

Let $d={\mathrm{deg}}_G(v^{\ast })$, then:

• $|V^{\prime }|=n-1+d\le 2n-2$.

Correctness of the Reduction

We prove:

(⇒) If $G$ has a Hamiltonian Cycle, then $G^{\prime }$ has a Path of Length $n$

Suppose $G$ has a Hamiltonian cycle:

where each $v_i$ is distinct and $v_1=v^{\ast }$.

In the cycle:

• $v_2$ and $v_n$ are neighbors of $v^{\ast }$ in $G$.
• In $G^{\prime }$, the edges $(v^{\ast },v_2)$ and $(v_n,v^{\ast })$ are replaced by:
  • $({\hat{v}}_2,v_2)$,
  • $(v_n,{\hat{v}}_n)$, where ${\hat{v}}_2$ and ${\hat{v}}_n$ are new vertices.

Define the path in $G^{\prime }$:

• This is a simple path,
• Contains $n+1$ vertices → path of length $n$,
• All edges exist in $G^{\prime }$.

Thus, $G^{\prime }$ contains a simple path of length $n$.

(⇐) If $G^{\prime }$ has a Path of Length $n$, then $G$ has a Hamiltonian Cycle

Suppose $G^{\prime }$ has a simple path:

with $n+1$ distinct vertices.

Note:

• we only have $n-1$ nodes originally from $G$, so at least $2$ of them are new.

• The “hat” nodes ${\hat{w}}_i$ have degree 1 in $G^{\prime }$.
• Therefore, they must appear at the endpoints of the path.

So:

• $u_0={\hat{w}}_a$, $u_n={\hat{w}}_b$ for some neighbors $w_a,w_b$ of $v^{\ast }$,
• $u_1=w_a$, $u_{n-1}=w_b$.

The subpath:

consists of $n-1$ distinct vertices from $V\setminus \{v^{\ast }\}$. Since there are exactly $n-1$ such vertices, this must be a Hamiltonian path in $G-\{v^{\ast }\}$.

To complete a Hamiltonian cycle in $G$:

• Re-insert $v^{\ast }$,
• Add edges $(v^{\ast },w_a)$ and $(w_b,v^{\ast })$, which exist in $G$ by construction.

Thus, the cycle:

is a Hamiltonian cycle in $G$.

Conclusion

We have shown that the Hamiltonian Cycle problem can be reduced in polynomial time to the Long-Path problem:

• If Long-Path can be solved in time $t(N)$,
• Then Hamiltonian Cycle can be solved in time $t(2n-2)+\mathcal{O}(n^2)$,
• Therefore, Long-Path is NP-complete.

Solving the Hamiltonian Cycle Problem via Dynamic Programming

The Hamiltonian Cycle problem asks whether a given graph $G=(V,E)$ contains a simple cycle that visits every vertex exactly once.

Although this problem is NP-complete, we can solve it in exponential time using dynamic programming (DP), specifically via a method similar to the Held-Karp algorithm. While this is not efficient for large graphs, it is significantly better than brute-force enumeration of all permutations.

Dynamic Programming Strategy

We fix an arbitrary starting vertex $u\in V$ and build up solutions by considering:

• Subsets of vertices $S\subseteq V$ such that $u\in S$, and
• A destination vertex $w\in S$, $w\ne u$ if $|S|>1$.

DP State Definition

Let:

That is, $f(S,w)$ indicates whether there’s a path that:

• Starts at $u$,
• Ends at $w$,
• Visits every vertex in $S$ exactly once.

Base Case

We initialize:

• $f(\{u\},u)=\text{YES}$ — the trivial path starting and ending at $u$, visiting only $u$.

Recurrence Relation

For all $S\subseteq V$ with $u\in S$ and $|S|>1$, and for all $w\in S$, compute:

In words:

• We can extend a valid path ending at $w^{\prime }$ in $S\setminus \{w\}$ to a path ending at $w$ by appending the edge $(w^{\prime },w)$, if such an edge exists.

Final Step: Detecting a Hamiltonian Cycle

After computing all $f(S,w)$, we check:

This indicates:

• A path from $u$ to $w$ visiting all vertices (Hamiltonian path), and
• A closing edge $(w,u)$, completing the Hamiltonian cycle.

Time and Space Complexity

Let $n=|V|$. Then:

• Number of states: $2^n$ subsets $S$ For each $S$, at most $n$ values of $w$ → $O(n\cdot 2^n)$ total states

• Time per state: For each $f(S,w)$, we may consider up to $n$ predecessors $w^{\prime }\in S\setminus \{w\}$ → $O(n)$ per state

• Total time complexity:

  $$O(n^2\cdot 2^n)$$

• Space complexity:

  $$O(n\cdot 2^n)$$

  to store the DP table.

Summary

This is one of the most efficient known exact algorithms for solving the Hamiltonian Cycle problem, thanks to its clever use of subproblem reuse via dynamic programming.

Long-Path via Randomized Coloring

We consider the Long-Path problem:

Given an undirected graph $G=(V,E)$ and an integer $B$, determine whether $G$ contains a simple path of length at least $B$.

Motivation

A dynamic programming approach for Long-Path (based on subset-DP) runs in time $O(n^{B+3})$, which is exponential in $B$. This becomes impractical for moderate values of $B$, though it works fine if $B$ is extremely small.

We want an algorithm with runtime $O(C^B\cdot \text{poly}(n))$ for some constant $C$, which would be polynomial when $B=O(\log n)$.

Randomized Approach: Color Coding

Key Idea

We randomly color the graph and search for a colorful path - a path where all $k$ vertices have distinct colors.

Let $k=B+1$. We seek a path of length $k-1$, using $k$ colors.

Probability That a Path Is Colorful

Suppose the graph contains a path $P$ of length $k-1$. Let us randomly color each vertex independently with a color in $\{1,\dots ,k\}$:

• There are $k^k$ possible colorings of the $k$ vertices on $P$.

• Exactly $k!$ of them assign distinct colors to all vertices on $P$, i.e., make $P$ colorful.

• So,

  $$\mathrm{Pr}[P\text{ is colorful}]=\frac{k!}{k^k}$$

Using Stirling’s approximation $k!\approx \sqrt{2\pi k}\cdot (k/e{)}^k$, we get:

Therefore, a lower bound is:

This means that the chance of a particular path becoming colorful under a random coloring is at least $e^{-k}$.

Monte Carlo Algorithm for Long-Path

1. Let $k=B+1$.
2. Repeat the following $\lceil \lambda e^k\rceil$ times:
   • Randomly color the vertices of $G$ using $k$ colors.
   • Check whether the graph contains a colorful path of length $k-1$.
   • If such a path is found, return YES.
3. If no colorful path is found in any iteration, return NO.

Correctness

• If the algorithm returns YES, the graph indeed contains a path of length $B$. (Because colorful paths are simple paths by definition.)

• If the graph contains a path of length $B$, then with probability at least $e^{-k}$, one random coloring will make some such path colorful.

• The probability that none of the $\lambda e^k$ trials succeeds is:

  $$(1-e^{-k}{)}^{\lambda e^k}\le e^{-\lambda }$$

  using the inequality $(1-x{)}^r\le e^{-xr}$.

So the error probability is at most $e^{-\lambda }$. This is a Monte Carlo algorithm: it may return NO incorrectly with small probability, but never returns YES incorrectly.

Runtime

The only missing piece is how to check for a colorful path in each iteration.

• This will be handled in the next lecture, where we will show how to check for the existence of a colorful path of length $k-1$ in time $$O(2^k\cdot k\cdot m)$$ where $m=|E|$, using a dynamic programming approach over subsets of colors.

Thus, the total runtime becomes:

This is polynomial in $n$ when $k=O(\log n)$, i.e., when $B=O(\log n)$.

Summary

• We can solve Long-Path in randomized FPT time using color coding.
• Error probability is at most $e^{-\lambda }$, with no false positives.
• Runtime is efficient for small $B$, especially $B=O(\log n)$.
• In the next lecture, we’ll see how to efficiently check for colorful paths in a given coloring.

Continue here: 20 Detecting Colorful Paths using DP, Flow Networks