For an undirected graph that consists of partial paths such that each vertex is a part of one of those paths and that there are edges between all the paths, is there an efficient algorithm to connect all the paths to form one hamiltonian cycle?
closed as off-topic by Tsuyoshi Ito, R B, Kristoffer Arnsfelt Hansen, Kaveh, David Eppstein Nov 19 '14 at 20:25
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Tsuyoshi Ito, R B, Kristoffer Arnsfelt Hansen, Kaveh, David Eppstein
From the comment above: you can easily prove that your problem is NP-complete. If you don't like the degenerated path solution (path of length zero) as correctly suggested by Yixin; and you also want to force that the paths are included in the Hamiltonian cycle; you can use an easy reduction from the Hamiltonian cycle problem on directed graphs (which is obviously NPC).
Given a graph $G$ replace each node with a path of length two (three nodes) and mark one of its enpoint as the ingoing endpoint and the other as the outgoing endpoint. Now simply connect the endpoints of the paths according to the original graph $G$: for a directed edge $u\to v$ you will connect the outgoing endpoint of the path corresponding to $u$ to the incoming endpoint of the path corresponding to $v$. The resulting (undirected) graph has an Hamiltonian cycle (which by construction must traverse every path, because the middle node must be included) if and only if the original digraph $G$ has an Hamiltonian cycle.