How to find a cycle containing a set of nodes in a graph?

Question

Given a graph undirected G = (V,E) and a set of nodes P. I need to find a cycle (not the shortest length cycle) containing these nodes? How do I find this cycle?

Answer 1

I would probably start designing the algorithm by choosing the first node in P (let's call it P[0]), then running a depth-first search from P[0], taking note of anytime P[0] is again reached. You would have to store the path taken to re-reach P[0] (or at least whether the other nodes of P have been reached) so that you know that any cycle you find contains all the nodes in P. Running time should be the same as for depth-first search, which I believe is O(V + E).

Someone may come up with a better solution, and certain heuristics might be applied to help, but that should get you started. (For instance, you may conclude you should start at the node of P with the fewest edges instead of starting at P[0].)

Edit:

One more thing I thought of... When you reach another node in P via your depth-first search, there is no need for the DFS ever to "start over" from the very beginning or to consider paths that do not include this newly-found node. This property could help your algorithm terminate more quickly in the case where no such cycle exists.

Further edit:

Never mind the last edit -- it would only work if it can be ascertained that there is no node in P on a different path between P[0] and the node in P reached that cannot be reached another way, and we wouldn't know that for sure without doing the whole DFS.

Regarding the answer about Hamiltonian cycles, I don't know how the cycle detection in the problem at hand is NP-complete. Yes, we would have to traverse the entire graph (all vertices and edges) reachable from the start point to determine whether a cycle meeting the criteria of the problem at hand exists. Further, we would need to know upon coming in contact with a previously-visited vertex what the "forward path" of the vertex would be to determine whether there is a cycle meeting the criteria. Since we don't care about the shortest such cycle, though, I'm not sure how we are necessarily trying to find a Hamiltonian cycle. Care to enlighten?

Answer 2

Contains Hamiltonian Cycle (for P = V), hence the decision problem (just knowing if there is such a thing) is NP-complete. So there is no efficient algorithm unless P = NP.