3
$\begingroup$

This question is motivated by a problem on a local programming competition (you can find the original problem statement here: http://maratona.algartelecom.com.br/files/12maratona.zip , problem E on the pdf, but it's in portuguese).

Basically the problem is: Given an initial complete graph with N vertices and a list of K edges removed from this graph, find the number of possible Hamiltonian cycles.

After much thinking during and after the competition, I could not find a solution to the problem.

The number of Hamiltonian cycles on a complete graph is (N-1)!/2 (at least I was able to arrive to this result myself during the contest haha).

It seems to me that if you take only one edge out, the result would be (N-1)!/2 - (N-2)! Reasoning behind it: suppose a complete graph with vertices 1, 2, 3 and 4, if you take out edge 2-3, you can calculate how many hamiltonian cycles are there using that edge by considering it a vertice, thus you would have "vertices" 1, (2,3) and 4. There are 3! ways of ordering them, but since every "rotation" of a path (ex: 1-(2,3)-4 and (2,3)-4-1) use the same edges, there are 3 rotations possible in this case, thus it becomes 3!/3 Also every "reverse" cycle use the same edges (ex: 1-(2,3)-4 and 4-(2,3)-1), so it becomes 3!/3*2, and since you can arrive the (2,3) both from any side, it would become 3!*2/3*2 = 2! (more generally, (N-2)!). This seems to work, please point out any mistake I've made.

The problem is that, when you remove multiple edges, you are recounting the removal of some paths if you do this for each one (ex: if you remove 2-3 and 4-5, you are counting twice the removal of all the cycles that use both edges). Also, it gets more complicated if you remove 3 or more edges from the same vertex since no path can use all of them.

I could not get any further than this. Please, if you can help, I also ask you to explain me the thought process to arrive at the solution (or any reading that can help me doing this).

Edit: Adding problem constraints The number of vertices in the problem is at most 300 (therefore, maximum 44850 initial edges). The maximum number of edges taken out is 15.

$\endgroup$
1
$\begingroup$

This looks a lot like the way you determine the chromatic polynomial, but in a some sense "reversed": you know the values of your most "complicated" graphs instead of iterating until you have reached the simplest ones.

Consider one edge $e$, then the number of hamiltonian cycles in $G$ equals the number of cycles in $G-e$ (those that do NOT use the edge) plus the number of cycles in $G/e$ (those that DO use the edge).

This can be transformed into a recursive algorithm: you know the values for the complete graphs, and all other intermediate values you require are the result of removing a smaller list of edges from a smaller complete graph.

However this will not perform at all on anything but the smallest examples and it certainly will not give you anything like a closed formula for the number of hamiltonian cycles. I am not at all sure if this is an acceptable solution.

EDITED AFTER REQUEST FOR DETAILS:

Consider next pseudocode.

int function h(int n, List l)
{
  if (l is empty) { return number of hamilton cycles in K_n }
  create new list lNew;
  return h(n, l minus last element) - h(n - 1, lNew);
}

This function $h$ calculates the number of hamiltonian cycles in $K_n$ when the edges of the list $l$ are missing. You use the recurrence $h(G-e)=h(G)-h(G/e)$, so you repeatedly put one edge back into the graph until you have put back everything. You have to decide on how to represent the edges on the list. One option is to represent each edge on $l$ simply as a pair of numbers in the range $1..n$. The only tricky part is the creation of the list $lNew$. You cannot just copy its elements from the list $l$, since they refer to edges of a $K_{n-1}$ after the recursion, so depending on the edge you are removing you need to manipulate the list elements.

I have no clue how this will perform with the numbers you mention. The most important thing will be that the list of edges is not too long, since that will determine the depth of the recursion. Be sure to use some kind of 'big integer' arithmetic or find other ways to avoid large numbers.

$\endgroup$
  • $\begingroup$ This is what I thought. My problem is: how to do this recursion? Cause if you take one edge and then recur, I don't see a clear way of taking another edge. Unless it is supposed to be some clever brute force solution. (If it helps the max N is 300, meaning at most 44850 edges and the maximum number of edges taken out is 15). $\endgroup$ – Alvaro Nov 25 '13 at 11:56
  • $\begingroup$ I have edited the answer with some more details, but the rest is really up to you. $\endgroup$ – Leen Droogendijk Nov 26 '13 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.