19.2. Hamiltonian Cycle

As a first illustration of how the inclusion-exclusion principle can be used as an algorithmic tool, we show how to design an algorithm for the Hamiltonian cycle problem. Given a graph \(G\), a Hamiltonian cycle in \(G\) is a simple cycle in \(G\) that visits every vertex of \(G\). Since this is a special case of the travelling salesman problem, we can use the dynamic programming algorithm from Section 18.1 to solve this problem in \(O^*(2^n)\) time. As pointed out in Section 18.1, however, this algorithm uses exponential space and thus is not practical for any non-trivial input. Here, we show how to use inclusion-exclusion to obtain an \(O^*(2^n)\)-time algorithm that uses only linear space.

We will first focus on simply deciding whether there exists a Hamiltonian cycle. This is easily done using inclusion-exclusion: We will develop an algorithm that can count the number of Hamiltonian cycles in \(G\). Clearly, there exists a Hamiltonian cycle if and only if this count is positive. Something that is quite easy to do when using dynamic programming but poses some challenges when using inclusion-exclusion is actually finding a Hamiltonian cycle. The reason is that the dynamic programming solution, using exponential space, essentially keeps enough of a description of the solution to each possible subproblem that we can construct a solution simply by "tracing a path" through the dynamic programming table. You should have seen this many times in the discussion of dynamic programming in CSCI 3110, so I will not discuss this here. An inclusion-exclusion algorithm keeps very little information about what the objects it counts look like, so this approach of constructing a solution is infeasible.

Thankfully, The Hamiltonian cycle problem has a useful property, called self-reducibility. Once we conclude that there exists a Hamiltonian cycle, constructing such a cycle is a basic edge selection problem again: We need to find the edges that belong to a Hamiltonian cycle. We do this by inspecting every edge \(e\). If the graph \(G - e\) has a Hamiltonian cycle, then this is clearly also a Hamiltonian cycle in \(G\), so we remove \(e\) from \(G\) and find a Hamiltonian cycle in \(G - e\). If \(G - e\) has no Hamiltonian cycle, then since \(G\) has a Hamiltonian cycle, \(e\) must be part of every such cycle. We keep \(e\) and test whether we can safely remove the next edge. We'll discuss this approach in more detail at the end of this section.