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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
