2

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.

Shawn McClelland
  • 39
  • 1
  • 5

1 Answers1

8

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

The O(2k)-based solution uses the inclusion-exclusion principle. Given that there are k forbidden edges, there are 2k 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 23=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.

xan
  • 7,511
  • 2
  • 32
  • 45
  • Wow, excellent! That's was a MUCH better explanation than I have seen before. And actually made it through my thick skull. Thank you! – Shawn McClelland May 20 '11 at 16:13
  • Okay, finally got the large data set solved :). The part I'm trying to understand is the reasoning for the (-1)^|s|, why would every all the odd # elements be subtracted and the even added? I'll have to read more about the inclusion-exclusion principle - obviously I don't have the background in math, I'm a neurobiology/biochemist. – Shawn McClelland May 20 '11 at 16:50
  • @xan I know this comment comes out of nowhere, but it think the answer should be `f(s) * (-1)^(|s|+1)` (according to wikipedia)... – Rontogiannis Aristofanis Mar 13 '14 at 18:16
  • @RontogiannisAristofanis You may have to expand on that. I think this sum is different from the generic inclusion/exclusion, if that's what you're referring to, because this is subtractive rather than additive. – xan Mar 13 '14 at 22:42
  • @xan you are right, I double checked the inclusion-exclusion principle article. What I proposed was correct, but not applicable in the current problem :) – Rontogiannis Aristofanis Mar 14 '14 at 14:35
  • can you define chain? so lets say my set under consideration is {A, B}; A => 1<-> 2 B => 2<->3. Is that one chain (1-2-3)? – quickbrownfox Oct 04 '15 at 08:18
  • @patmyback yes, a chain is a sequence of connected edges – xan Oct 04 '15 at 16:06