How to find the number of Hamiltonian cycles that do not use forbidden edges?

Question

This question actually rephrases that one . The problem with code jams is this:

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

The direct approach DP O(2^N*N^2) does not work for such N. It seems that the solutions are O(2^K) . Does anyone know how to solve this problem?

Answer 1

Find out for each subset S of forbidden edges how many Hamiltonian cycles exist that use all edges of S. If we solve this subproblem, then we solve the inclusion exclusion exclusion formula problem.

Now, how do we solve the subtask? Let all edges of S be drawn. If there is a vertex of degree greater 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 single vertex, loop, or simple path.

If a cycle exists, then it must go through all the vertices, otherwise we will not be able to complete the Hamiltonian cycle. If so, the answer is 2. (The cycle can go in 2 directions.) Otherwise, the answer will be 0.

The case remains when there exist paths c and k are the only vertices. To complete the Hamilton cycle, we must choose the direction of each path ( 2 ^ c ), and then choose the order of the components. We have c + k components, so they can be rearranged in the path (c + k)! . But we are interested in cycles, so we do not distinguish between orderings that turn to each other by cyclic shifts. (So ​​(1,2,3), (2,3,1) and (3,1,2) are the same.) This 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 the bmerry solution (very clean code, by the way).

Answer 2

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

This is NP Complete problems, which in simple words mean that their quick fix is ​​not known.

The trivial heuristic algorithm for finding Hamiltonian paths is to construct the path abc ... and expand it until it becomes impossible; when the path abc ... xyz cannot be continued, because all neighbors of z are already on the path, one returns one step, removing the edge yz and expanding the path with the other neighbor y; if none of the options leads to the Hamiltonian path, then it takes another step backward, removing the edge xy and expanding the path with another neighbor x, etc. This algorithm will certainly find the Hamiltonian path (if any), but it works in exponential time.

For additional NP verification. Complete chapter of the “Introduction to Algos” issue from Cormen