2
$\begingroup$

Let's say we have given unweighted directed graph with $N$ nodes and $M$ edges, and we want to find the $K$-th hamiltonian circuit, ordered in lexicographical order.

For example, if we have complete graph with $4$ nodes, and $12$ edges. The smallest hamiltonian circuit is $1 - 2 - 3 - 4$, the second one is $1 - 2 - 4 - 3$. Since finding hamiltonian circuit is NP Hard, what is the best complexity we can get this algorithm at?

Hamiltonian circuit is path that visits each node exactly once.

For the purpose of the problem, the circuit should begin in node $1$

What I think

If we have adjacent list of nodes connected to node $1$, sorted, then the permutations numbered from $[1, x]$ will pass in the first node, the on the second node the permutations numbered $[x, y]$ will pass the second node, etc..

Now our task is actually to find the $x, y...$ And we can solve for the second node (that we called from node $1$) for each of nodes adjacent to it, but this leads us to time complexity of $O(N!)$. Can we do it faster?

$\endgroup$
  • $\begingroup$ A complete graph with 4 nodes has 6 edges. (A complete graph with 5 nodes has 10 edges, is that what you meant?) $\endgroup$ – j_random_hacker Oct 9 '17 at 15:52
  • $\begingroup$ @j_random_hacker No, Let's say we have (only for example) complete graph with 5 nodes (and 20 edges, because the graph is directed) now we have exactly $4!$ possible permutations of hamiltonian circuit (not $5!$ because our starting point 1 is fixed), and from all those $4!$ permutations of hamiltonian circuit we want to return only the k-th in lexicographical order. $\endgroup$ – someone12321 Oct 9 '17 at 18:09
  • $\begingroup$ Sorry, I missed that the graph was directed. In that case, a complete graph on 4 nodes has 12 edges (not the 6 I claimed before, or the 10 you have stated in your question currently). $\endgroup$ – j_random_hacker Oct 9 '17 at 19:27
1
$\begingroup$

Counting the number of Hamiltonian circuits in a graph is $\mathsf{\#P}$-hard (see for example this answer). Your problem is even harder, since we can use your problem together with binary search to count the number of Hamiltonian circuits in a given graph.

As an aside, let me mention that listing things in lexicographical order might be harder than listing them in any order. A case in point is the complexity of finding a [maximal independent set], which is an independent set which cannot be enlarged (but not necessarily one which has maximum size). A maximal independent set can easily be found by going over the vertices in some arbitrary order, putting the problem in the complexity class $\mathsf{P}$. This algorithm can be improved, and in fact a maximal independent set can be found in $\mathsf{NC^2}$. In contrast, finding the lexicographically first maximal independent set (that is, deciding whether a given vertex belongs to this set) is $\mathsf{P}$-complete.

$\endgroup$
  • $\begingroup$ Do you recommend starting point how to start solving this problem, I was thinking about some dp with bitmasks which would have complexity $O(2^N)$, but I can't come up with the states and other stuff. $\endgroup$ – someone12321 Oct 9 '17 at 18:06
  • $\begingroup$ I would start by searching the literature for exponential time algorithms that count the number of Hamiltonian circuits. Perhaps some of them can be adapted to solve your problem. $\endgroup$ – Yuval Filmus Oct 9 '17 at 18:08
  • $\begingroup$ Which literature do you recommend? $\endgroup$ – someone12321 Oct 9 '17 at 18:10
  • $\begingroup$ I don't have anything particular in mind. $\endgroup$ – Yuval Filmus Oct 9 '17 at 18:12

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.