CODEWITHSUNDEEP
algorithmgraphhamiltonian-cycle
Ezio
Ezio

Reputation: 753

How to Find Number of Hamiltonian Paths in a graph?

I am trying out this Google Codejam problem which says to find out number of hamiltonian paths if we remove k edges from a complete graph

link to Question

https://code.google.com/codejam/contest/32004/dashboard#s=p2

I figured out we can use inclusion exclusion principle to find out the number

but my problem is how to determine the number of path when we are considering that some 'x' number of edges have been removed from the complete graph(the edges removed are given)

Upvotes: 1

Views: 2169

Answers (1)

kraskevich
kraskevich

Reputation: 18556

The idea is to count permutations instead of counting paths. This way, each path would be taken into account 2*n times.

The total number if permutations is n!.

Let's use the inculsion-exlusion principle to count bad cycles. If one edge is banned, there are 2*n * (n-2)! paths that contain this edge (we place two adjacent vertices together and the rest goes anywhere).

If there are several banned edges, all vetrices are divided into several independent groups (they form chains connected by these edges). There are two ways to place each group (as it can be reversed). All groups can be arbitrarily permuted with each other. The rest of the elements can be placed anywhere (it would contribute as a binomial coefficient times some factorial). There is one more caveat: a chain can wrap around. But there can be at most one such chain. So we can iterate over the chain that wraps and count the number of ways to place the rest using the algorithm described above.

Upvotes: 0

Related Questions