-2
$\begingroup$

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?

$\endgroup$

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
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Can you make your question more precise? I.e; is your graph a family of paths and you are supposed to add edges to it (these are non-edges until you add them) to make it a cycle? Or do you have a "partial solution" to Hamiltonian Cycle - a system of paths, inside the input graph, and you are trying to extend it to a Hamiltonian cycle? $\endgroup$ – daniello Oct 24 '14 at 6:16
  • $\begingroup$ @daniello It's a partial solution to a Hamiltonian Cycle; the edges are there. I have to decide which of the remaining edges to choose for each path. $\endgroup$ – Izzah Leari Oct 24 '14 at 9:36
  • 2
    $\begingroup$ If I understood the problem well, it is still NP-complete: pick the Hamiltonian cycle problem on a directed graph $G$ with max degree 3 (indegree + outdegree of every node is $\leq 3$); and replace each node $u$ of $G$ with two nodes $\{u_{in},u_{out}\}$ and build a simple path $P_u$ of length one between them. Then connect all the paths $P_u$ according to the original graph $G$. The resulting graph has an Hamiltonian cycle (connecting all the simple paths) if and only if the original problem has an Hamiltonian cycle. $\endgroup$ – Marzio De Biasi Oct 24 '14 at 10:31
  • 2
    $\begingroup$ What's the real difference for the original problem? You can replace every path by an edge (omitting all internal vertices); you can also treat every vertex as a degenerated path. $\endgroup$ – Yixin Cao Oct 24 '14 at 10:35
  • $\begingroup$ @MarzioDeBiasi NP-complete? Oh dear. Thanks. $\endgroup$ – Izzah Leari Oct 24 '14 at 10:54
0
$\begingroup$

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.

$\endgroup$

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