How do I find the number of Hamiltonian cycles that do not use “forbidden” edges?

Question

This question actually rephrases that one. The code jam problem is the following:

You are given a complete undirected graph with N nodes and K "forbidden" edges. N <= 300, K <= 15. Find the number of Hamiltonian cycles in the graph that do not use any of the K "forbidden" edges.

The straightforward DP approach of O(2^N*N^2) does not work for such N. It looks like that the winning solutions are O(2^K). Does anybody know how to solve this problem ?

Answer 1

Let's find out for each subset S of forbidden edges, how many Hamiltonian cycles there exist, that use all edges of S. If we solve this subtask then we'll solve the problem by inclusion-exclusion formula.

Now how do we solve the subtask? Let's draw all edges of S. If there exist a vertex of degree more than 2, then obviously we cannot complete the cycle and the answer is 0. Otherwise the graph is divided into connected components. Each component is a sole vertex, a cycle or a simple path.

If there exists a cycle, then it must pass through all vertices, otherwise we won't be able to complete the Hamiltonian cycle. If this is the case, the answer is 2. (The cycle can be traversed in 2 directions.) Otherwise the answer is 0.

The remaining case is when there are c paths and k sole vertices. To complete the Hamiltonian cycle we must choose the direction of each path (2^c ways) and then choose the order of components. We've got c+k components, so they can be rearranged in (c+k)! ways. But we are interested in cycles, so we don't distinguish the orderings which turn into one another by cyclic shifts. (So (1,2,3), (2,3,1) and (3,1,2) are the same.) It means that we must divide the answer by the number of shifts, c+k. So the answer (to the subtask) is 2^c (c+k-1)!.

This idea is implemented in bmerry's solution (very clean code, btw).

Answer 2

Hamiltonian cycle problem is a special case of travelling salesman problem (obtained by setting the distance between two cities to a finite constant if they are adjacent and infinity otherwise.)

These are NP Complete problems which in simple words means no fast solution to them is known.

A trivial heuristic algorithm for locating Hamiltonian paths is to construct a path abc... and extend it until no longer possible; when the path abc... xyz cannot be extended any longer because all neighbours of z already lie in the path, one goes back one step, removing the edge yz and extending the path with a different neighbour of y; if no choice produces a Hamiltonian path, then one takes a further step back, removing the edge xy and extending the path with a different neighbour of x, and so on. This algorithm will certainly find an Hamiltonian path (if any) but it runs in exponential time.

For more check NP Complete problem chapter of "Introduction to Algos" by Cormen