19.2.1. Deciding Whether a Hamiltonian Cycle Exists

First let us consider the decision version of the problem: We want to decide whether \(G\) has a Hamiltonian cycle even though we may not know how to find one. Let \(s\) be a fixed vertex of \(G\). \(G\) has a Hamiltonian cycle if and only if there exists a Hamiltonian path from \(s\) to a neighbour of \(s\); a Hamiltonian path is a simple path that visits every vertex of \(G\). To decide whether there exists a Hamiltonian path from \(s\) to a neighbour of \(s\), it suffices to count these paths; clearly, there exists a Hamiltonian path from \(s\) to a neighbour of \(s\) if and only if the count of these paths is strictly positive.

What makes finding a Hamiltonian cycle or path difficult is the requirement that the cycle or path should be simple. If we relax this requirement to looking for a walk of length \(n-1\) from \(s\) to \(v\), we can easily count these walks in \(O\bigl(n^3\bigr)\) time. A walk of length \(k\) is a sequence of vertices \(\langle v_0, \ldots, v_k \rangle\) such that \((v_{i-1}, v_i)\) is an edge in \(G\) for all \(1 \le i \le k\); there is no requirement that no vertex or edge occurs more than once in this sequence. For any vertex \(v \in G\) and any integer \(\ell \ge 0\), let \(W(v,\ell)\) be the number of walks of length \(\ell\) from \(s\) to \(v\).

Lemma 19.3: Given a graph \(G\) and a vertex \(s \in G\), it takes \(O\bigl(n^3\bigr)\) time and linear space to compute \(W(v,n-1)\) for all \(v \in G\).

Proof: We use dynamic programming to construct a table \(W\) of size \(O\bigl(n^2\bigr)\) storing all values \(W(v,\ell)\).

For \(\ell = 0\), there exists a walk of length \(0\) from \(s\) to \(v\) only if \(v = s\) and there exists exactly one such walk from \(s\) to \(s\). Thus,

\[\begin{aligned} W(s,0) &= 1\\ W(v,0) &= 0 && \forall v \ne s. \end{aligned}\]

Clearly, filling in these values takes \(O(n)\) time.

For \(\ell > 0\), any walk of length \(\ell\) from \(s\) to \(v\) is a walk of length \(\ell-1\) from \(s\) to some neighbour \(u\) of \(v\) followed by the edge \((u,v)\). Thus,

\[W(v,\ell) = \sum_{u \in N(v)} W(u,\ell-1).\]

Given the values \(W(u,\ell-1)\) for all \(u \in V\), computing \(W(v,\ell)\) using this equation takes \(O(n)\) time. Since there are \(n(n-1)\) entries \(W(v,\ell)\) with \(\ell > 0\) to be computed, filling in the table \(W\) takes \(O\bigl(n^3\bigr)\) time in total.

To obtain the final space bound, observe that the final output is clearly a table of size \(n\) storing only the values \(W(v,n-1)\) for all \(v \in G\). While the algorithm runs, observe that computing the values \(W(v,\ell)\) for all \(v \in G\) only requires the values \(W(u,\ell-1)\) for all \(u \in G\). Thus, we never need to hold more than the current column and the previous column of the table \(W\) in memory; all other columns can be discarded. Thus, while the algorithm runs, it stores only \(2n\) entries of the table \(W\) and thus uses linear space. ▨

How do we go from counting walks of length \(n-1\) to counting Hamiltonian paths? First, we strengthen Lemma 19.3 slightly so it allows us to count walks that are not allowed to visit certain vertices. Let \(U \subseteq V\) be a subset of vertices and let \(W_U(v,\ell)\) be the number of walks of length \(\ell\) from \(s\) to \(v\) that visit only vertices in \(U\). Such a walk may not visit all vertices in \(U\) but it is not allowed to visit any vertex not in \(U\).

Lemma 19.4: Given a graph \(G\), a vertex \(s \in G\), and a subset \({s} \subseteq U \subseteq V\), it takes \(O\bigl(n^3\bigr)\) time and linear space to compute \(W_U(v,n-1)\) for all \(v \in G\).

Proof: If \(v \notin U\), we can immediately report \(W(v,n-1) = 0\) because every walk from \(s\) to \(u\) visits \(u\).

If \(v \in U\), then observe that \(W_U(v,n-1)\) is exactly the number of walks of length \(n-1\) from \(s\) to \(v\) in \(G[U]\). Thus, we construct \(G[U]\) and then apply the algorithm from Lemma 19.3 to \(G[U]\) to compute \(W_U(v,n-1)\) for all \(v \in U\). ▨

Now we are ready to apply inclusion-exclusion to count the number of Hamiltonian paths from \(s\) to \(v\) for all \(v \in V\). The set of objects we consider is all walks of length \(n-1\) from \(s\) to \(v\). We say that such a walk has property \(P_u\) for some vertex \(u \in V\) if it visits \(u\). Let \(\mathcal{P}\) be the set of these properties and let \(\mathcal{Q}_U = \{ P_u \mid u \in U \}\) for any subset \(U \subseteq V\). Then the walks of length \(n-1\) from \(s\) to \(v\) that have none of the properties in \(\mathcal{Q}_U\) are exactly the walks of length \(n-1\) from \(s\) to \(v\) that visit only vertices in \(V \setminus U\). Thus, \(m_{\mathcal{Q}_U} = W_{V \setminus U}(v,n-1)\). A Hamiltonian path from \(s\) to \(v\) is a walk of length \(n-1\) from \(s\) to \(v\) that visits all vertices in \(G\) and thus has all of the properties in \(\mathcal{P}\). Thus, by Corollary 19.2, the number of Hamiltonian paths from \(s\) to \(v\) is

\[\sum_{U \subseteq V} (-1)^{|\mathcal{Q}_U|} m_{\mathcal{Q}_U} = \sum_{U \subseteq V} (-1)^{|U|} W_{V \setminus U}(v,n-1).\]

Lemma 19.5: It takes \(O^*(2^n)\) time and linear space to count the number of Hamiltonian paths from \(s\) to all vertices in \(G\).

Proof: We initialize a table \(H\) that stores the number of Hamiltonian paths from \(s\) to \(v\), for all \(v \in V\). Initially, \(H(v) = 0\), for all \(v \in V\). Then we iterate over all subsets \(U \subseteq V\) and run the algorithm from Lemma 19.4 to compute \(W_{V \setminus U}(v,n-1)\) for all \(v \in V\). This takes \(O\bigl(n^3\bigr)\) time and linear space. After computing \(W_{V \setminus U}(v,n-1)\) for all \(v \in V\), we update \(H(v) = H(v) + (-1)^{|U|}W_{V \setminus U}(v,n-1)\) for all \(v \in V\).

At any given point during the execution of the algortihm, we only need space for the table \(H\) plus the linear working space needed to compute the current set of values \(W_{V \setminus U}(v,n-1)\). Thus, the algorithm uses linear space.

We run the algorithm from Lemma 19.4 once for each subset \(U \subseteq V\). Since there are \(2^n\) such subsets, the algorithm takes \(O\bigl(2^n \cdot n^3\bigr) = O^*(2^n)\) time. ▨

As already observed, there exists a Hamiltonian cycle in \(G\) if and only if there exists a neighbour \(v\) of \(s\) such that the value \(H(v)\) computed in Lemma 19.5 is non-zero. This is a condition that is easily checked in linear time. Thus, we have

Corollary 19.6: It takes \(O^*(2^n)\) time and linear space to decide whether a graph \(G\) has a Hamiltonian cycle.