<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2014-10-25T20:03:32.830Z
2014-10-25T20:03:32.830Z
Marzio De Biasi
<p>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?</p>

CC BY-SA 3.0
2014-10-24T06:16:44.677Z
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?
daniello
CC BY-SA 3.0
2014-10-24T09:36:02.443Z
@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.
Izzah Leari
CC BY-SA 3.0
2014-10-24T10:31:33.940Z
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.
Marzio De Biasi
CC BY-SA 3.0
2014-10-24T10:35:07.630Z
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.
Yixin Cao
CC BY-SA 3.0
2014-10-24T10:54:02.710Z
@MarzioDeBiasi NP-complete? Oh dear. Thanks.
Izzah Leari
CC BY-SA 3.0
2014-10-24T12:18:30.623Z
@IzzahLeari: the "degenerated path" (suggested by Yixin) also works. Can I convert my comment to an answer?
Marzio De Biasi
<graph-theory><graph-algorithms><hamiltonian-paths>
Connecting partial paths to form a hamiltonian cycle
Izzah Leari
# Connecting partial paths to form a hamiltonian cycle

(Asked by: username_0 on 2014-10-24)

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?

**Tags:** graph-theory, graph-algorithms, hamiltonian-paths

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 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.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: @MarzioDeBiasi NP-complete? Oh dear. Thanks.  
> **username_2**: @IzzahLeari: the "degenerated path" (suggested by Yixin) also works. Can I convert my comment to an answer?  

---

## 1 answers

### Answer by username_2 on 2014-10-25. Score: 0 | Accepted answer

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.


---

