2
$\begingroup$

I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This problem is the Hamiltonian Path problem except it is only certain nodes that have to obey this principle. Let me know if there is a name for this problem or if anyone has an idea of how to efficiently do this in maybe polynomial time.

$\endgroup$

2 Answers 2

2
$\begingroup$

As D.W. says, it is NP-hard, so we don't expect the problem to have a polynomial time algorithm, but it is FPT:

You can solve it in time $O(2^{|A|} n^5)$ which is polynomial if you consider $|A|$ small, e.g. $|A| = O(\log n)$. The factor $n^5$ can be improved.

Check out the (very accessible) paper by Shortest Cycle Through Specified Elements. Björklund, Husfeldt, and Taslaman, 2012.

This uses exponential space in $|A|$, but there are ways around that (e.g. using inclusion-exclusion methods by Nederlof).

$\endgroup$
0
$\begingroup$

You can't do it in polynomial time (unless P = NP), since it is as hard as the Hamiltonian path problem (consider the special case where you must visit all nodes). One standard approach if you have to solve it in problem and the graph is small enough is to use a SAT solver.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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