2. Hamiltonian Cycles

Cycle that visits every node exactly once. NP-Complete ☠️.

Tip: some problems that seems to need a Hamiltonian solution can be reframed so that an Eulerian solution works instead.

Prerequisite: Inclusion Exclusion Principle

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k+1}\left(\sum _{1⩽i_1<\cdots <i_k⩽n}|A_{i_1}\cap \cdots \cap A_{i_k}|\right)$$

Example: $|A\cup B|=|A|+|B|-|A\cap B|$

Example: $|A\cup B\cup C|=$ $|A|+|B|+|C|$ $-|A\cap B|-|A\cap C|-|B\cap C|$ $+|A\cap B\cap C|$

From left to right: union; removing all double overlaps; add triple overlap back once

---

Held–Karp Algorithm

DP algorithm that cuts down checking for the existence of a Hamiltonian cycle from $\mathcal{O}(n!)$ to $\mathcal{O}(n^2{2}^n)$.

We fix a $u\in V$ as starting vertex (a cycle must contain all nodes).

State: $P[S][v]:=$ a Hamiltonian path exists for the subset $s$, typically represented as bitmask, ending on $v$

Base case: $P[u][u]=1$

Recurrence: $P[S\cup w][w]=P[S][v]\wedge (v,w)\in E$ for some $v$ ($\in S$)

Extraction: $P[V][v]=1$ for some $v$ with $(v,u)\in V$

Runtime:

• $\mathcal{O}(2^n\cdot n)$ for iterating over the dp table
• $\mathcal{O}(n)$ for iterating over all $n$ possible endings, where checking $(v,w)\in E$ is $\mathcal{O}(1)$ because we use an adjacency matrix Total: $\mathcal{O}(n^2{2}^n)$ Space complexity: $\mathcal{O}(n\cdot 2^n)$

Inclusion-Exclusion Hamiltonian Cycle Algorithm

$W_S:=\{$ walks of length $n$ in $G$ with start- and end nodes $s$ that don’t visit any nodes in $S$ $\}$

$W_S$ is easy to compute: We first raise the adjacency matrix to the $n$-th power to get the number of $n$-length walks between any two nodes (See [[11. Matrices and Graphs#11. Matrices and Graphs#Number of Walks|A&D/11. Matrices and Graphs]]). We then read off the entry $(s,s)$.

However, they aren’t all

• subtract those that are

Special Graph Types

Grid Graphs

Hamiltonian cycle $⟺$ # nodes even

If uneven: We can color in the graph with a chess board grid. A Hamiltonian cycle would have to alternatively visit light and dark shaded nodes. To form a cycle, it would need to visit equally many dark and light shaded nodes. However, if it is uneven, we have an uneven number of dark shaded and light shaded nodes.

If even: We orient the even edge vertically. We can then go from left to right multiple times while always returning to the starting edge:

n-Dimensional Hypercubes

Always have Hamiltonian cycles.

Dirac’s Theorem

Theorem

If $G=(V,E)$ is a graph with $|V|\ge 3$ vertices in which every vertex has at least $|V|/2$ neighbors, then $G$ is Hamiltonian.