19.2.2. Finding a Hamiltonian Cycle

Corollary 19.6 lets us decide whether there exists a Hamiltonian cycle but is unsatisfactory because it does not actually compute a Hamiltonian cycle. In contrast, the dynamic programming algorithm from Section 18.1 computes an optimal travelling salesman tour, not just its length.

In this subsection, we demonstrate how to use the method of self-reduction to not only decide whether there exists a Hamiltonian cycle in \(G\) but to find such a cycle if it exists. This increases the running time of the algorithm by a constant factor and thus maintains the \(O^*(2^n)\) running time of the algorithm.

If the decision algorithm returns that there is no Hamiltonian cycle in \(G\), then there is no need to try to find one. So assume that the decision algorithm answers that a Hamiltonian cycle exists. Then the basic idea is to remove edges from \(G\) one by one while maintaining that \(G\) has a Hamiltonian cycle. Once we cannot remove any edges anymore, the edges that are left are exactly the edges in a Hamiltonian cycle.

First we demonstrate how to apply this method at the cost of increasing the running time of the algorithm by a factor of \(m\). Then we will see how to reduce this factor to \(O(1)\).

Lemma 19.7: If \(G\) has a Hamiltonian cycle, then such a cycle can be found in \(O\bigl(2^n \cdot n^3 \cdot m\bigr)\) time and \(O(n)\) space.

Proof: We inspect the edges in \(G\) one at a time. For each inspected edge \(e\), we test whether \(G - e\) has a Hamiltonian cycle. If so, we remove \(e\) from \(G\) and thus effectively proceed to finding a Hamiltonian cycle in \(G - e \subseteq G\). Otherwise, \(e\) must be part of every Hamiltonian cycle in \(G\), so we do not remove \(e\).

This procedure clearly takes \(O\bigl(2^n \cdot n^3 \cdot m\bigr)\) time because it applies the algorithm from Corollary 19.6 \(m\) times. The final graph \(C \subseteq G\) produced by the algorithm has a Hamiltonian cycle because we remove an edge from \(G\) only if the resulting graph still has a Hamiltonian cycle. Thus, if \(C\) has \(n\) edges, then \(C\) is a Hamiltonian cycle.

To prove that \(C\) has \(n\) edges, assume for the sake of contradiction that \(C\) has more than \(n\) edges. Then let \(C' \subseteq C\) be a Hamiltonian cycle in \(C\) and let \(e\) be an edge of \(C\) that is not in \(C'\). Let \(G'\) be the current subgraph of \(G\) at the time we try to remove the edge \(e\). Then \(G' - e \supseteq C - e \supseteq C'\). Thus, \(G' - e\) has a Hamiltonian cycle and we remove \(e\) from \(G'\), a contradiction. ▨

To reduce the increase in the running time of the algorithm to a constant factor, we need to inspect the edges of \(G\) in a more careful order. First recall how Corollary 19.6 decides whether there exists a Hamiltonian cycle: It checks whether there exists a neighbour \(v\) of \(s\) such that \(G\) contains a Hamiltonian path \(P\) from \(s\) to \(v\). What we do now is construct this Hamiltonian path instead of a Hamiltonian cycle; the edge \((s,v)\) needed to complete the cycle can be added at the end of the algorithm.

Let \(P = \langle s = v_1, \ldots, v_n = v \rangle\). To construct \(P\), we need to find the predecessor \(v_i\) of every vertex \(v_{i+1}\), for all \(1 \le i \le n-1\). To find the predecessor \(v_{n-1}\) of \(v_n\), we need to identify an arbitrary neighbour \(v_{n-1}\) of \(v_n\) such that there exists a Hamiltonian path from \(s\) to \(v_{n-1}\) in \(G[V \setminus \{v_n\}]\). To find such a neighbour \(v_{n-1}\), we apply Lemma 19.5 to \(G[V \setminus \{v_n\}]\). To find \(v_{n-1}\)'s predecessor \(v_{n-2}\), we apply Lemma 19.5 to \(G[V \setminus \{v_{n-1}, v_n\}]\) and so on until we only have \(s\) and its successor \(v_1\) in \(P\) left. Finding \(v_i\) for \(i = n, n-1, \ldots, 3\) involves applying Lemma 19.5 to \(G[V_i]\), where \(V_i = \{v_1, \ldots, v_i\}\). Thus, this takes \(O\bigl(2^i \cdot n^3\bigr)\) time. Summing this over all \(n\) vertices in \(P\), the construction of \(P\) takes \(O\bigl(\sum_{i=3}^n 2^i \cdot n^3\bigr) = O\bigl(2^n \cdot n^3\bigr)\) time. This proves the following theorem:

Theorem 19.8: It takes \(O\bigl(2^n \cdot n^3\bigr) = O^*(2^n)\) time and linear space to decide whether a graph \(G\) has a Hamiltonian cycle and, if so, find such a cycle.