Show np-completeness of Disjoint Hamiltonian Path

Consider the problem of Disjoint Hamiltonian Path:

Input: A graph which may be directed or undirected

Output: Does this graph exist at least 2 Hamiltonian Paths that are edge-disjoint? Edge-disjoint means that no single edge is shared by two paths.

Show that Disjoint Hamiltonian Path is np-complete.

I have been told that this problem is np-complete, but I couldn't prove it is np-hard. I tried reducing the original Hamiltonian Path and Hamiltonian Cycle to this problem but I couldn't think of a solution.

I came up with the following reduction, not sure if it's the simplest but it is simple.

Suppose G is an undirected graph corresponding to an instance of HP. Now construct a new graph G' in the following way:

• Keep every vertex from G.
• For every edge (u,v) in G, create 4 additional vertices and connect them in the following way :

Now it is easy to see that if G has a Hamiltonian path, G' will have two edge-disjoint Hamiltonian paths, because every edge was replaced by some subgraph which itself has two edge-disjoint Hamiltonian paths (go straight or take the curvy edges). And if G' has a HP, then so does G because once you enter the subgraph corresponding to one of the original edges you have no choice but to get out of it on the other end, which corresponds to taking the original edge in G. The only "problem" that could occur is if the path were to start or end inside one of these subgraphs, but then we can just ignore the small part of the path which is inside and still get a HP for G.

And notice that G' has a HP => G has a HP => G' has two edge-disjoint HPs. Thus, G has a HP <=> G' has two edge-disjoint HPs.

The transformation can obviously be done in poly-time, thus your problem is NP-Hard.

The directed case is similar, just direct the edges in the transformed graph accordingly.