GCJ - Hamiltonian Cycles

Question

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.

Unfortunately the explanations of this here on stack and throughout the web are very insufficient. I can figure out HamCycles for a certain 'n' : (n-1)! / 2 .

And I can do the short set with dynamic programming.

But I don't get all the subset bologna, how to make it O^K? I'm in Python and have yet to decipher the C++ available. Eventually I'm sure I will take the time to learn C++ and then I will decipher it. But in the meantime, why can't someone explain this better somewhere on the web? They are always half explanations.

Answer 1

It might help if you point to the explanations that are lacking, but I'll try anyway...

The O(2^k)-based solution uses the inclusion-exclusion principle. Given that there are k forbidden edges, there are 2^k subsets of those edges, including the set itself and the empty set. For instance, if there were 3 forbidden edges: {A, B, C}, there would be 2³=8 subsets: {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

For each subset, you calculate the number of cycles that include at least all the edges in that subset . If the number of cycles containing edges s is f(s) and S is the set of all forbidden edges, then by the inclusion-exclusion principle, the number of cycles without any forbidden edges is:

 sum, for each subset s of S: f(s) * (-1)^|s|

where |s| is the number of elements in s. Put another way, the sum of the number of cycles with any edges minus the number of cycles with at least 1 forbidden edge plus the number with at least 2 forbidden edges, ...

Calculating f(s) is not trivial -- at least I didn't find an easy way to do it. You might stop and ponder it before reading on.

To calculate f(s), start with the number of permutations of the nodes not involved with any s nodes. If there are m such nodes, there are m! permutations, as you know. Call the number of permutations c.

Now examine the edges in s for chains. If there are any impossible combinations, such as a node involved with 3 edges or a subcycle within s, then f(s) is 0.

Otherwise, for each chain increment m by 1 and multiply c by 2m. (There are m places to put the chain in the existing permutations and the factor of 2 is because the chain can be forwards or backwards.) Finally, f(s) is c/(2m). The last division converts permutations to cycles.