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?