Graph that has 2 long paths

Question

We are given a graph G. We need to identify whether there exist two long paths inside the graph G, such that those paths span the entire vertex set of G.  The two paths need to be disjoint (have no vertices or edges in common. This also means that the two paths need to start and end at different vertices. For example, the following graph G does have two long paths:

0----0----0----0
|             |
0----0----0----0

As another example, following graph does not have "2 long path" structure:
0-----0      0------------0 0------------0

For this problem, either given a polynomial time algorithm, or show that the problem is NP complete.

Comments

Could you explain two paths further how these two criteria met in the example given in the question?
"Paths span the entire vertex set of G."
"The two paths need to be disjoint (have no vertices or edges in common."

A---B---C---D
|            |     
E---F---G---H

I could think of:
1st path:ABCD, 2nd Path:EFGH (span all vertices but 2 edges common)

Answer 1

So we are trying to figure out if we can find two paths in a graph that cover all vertices, but this path can't share any vertices or edges.

We can see that we can use another NP-hard problem called Hamiltonian path which finds the path in the graph that goes to every vertices exactly once.

We can take the Hamiltonian path graph and add a vertice that connects to the old vertices as we did in class. So we want to set a threshold for our problem to be equal to the number of original vertices + 1.

So if our original graph has a Hamiltonian path, that would mean there is a way to go through all the vertices exactly once. For the new graph for our problem, we can use the Hamiltonian path to find one of the two paths that we need and the path that is connected to the newly added vertex is the second path and that is how we can two disjoint graphs.

As we can see we can transform the Hamiltonian path problem into our problem. We can say that our problem is an NP-complete problem.

Answer 2

Given a graph G (V, E), we can construct G' (V ∪ {v1, v2}, E ∪ (v1, v2)),
s.t. ∀ v ∈ V, (v, v1) ∉ E, (v, v2) ∉ E.
In other word, we add an independent arc in G to get G'.

If G' has two long paths, it must have a path which is (v1, v2). Therefore, G has a Hamiltonian path.
If G has a Hamiltonian path, then G' must have two long paths, which are the Hamiltonian path in G and path v1v2.

Answer 3

 The two long paths in a graph problem(TLP) is NP-complete. 

1.  The problem is in NP:

Given two paths, we can verify in polynomial time that they cover all vertices and are disjoint simply by checking each path.

2. The problem is NP-hard:

Answer 4

The Hamiltonian Cycle problem, which is known to be NP-complete, can be reduced to the problem of finding two disjoint long paths. Create a new graph G' by duplicating each vertex in G and linking the appropriate duplicates with an edge given a graph G. Finding two distinct long pathways that cross all vertices in G' now corresponds to finding a Hamiltonian cycle in the original graph G. As a result, identifying two disjoint long pathways is an NP-hard issue.

Given a proposed solution consisting of two pathways P1 and P2, we can check for the following to see if they are disjoint and span all vertices in polynomial time:
-> Check that P1 and P2 do not contain any overlapping vertices or edges.
-> Vertex traversal: Verify that every vertex in G can be reached by traversing P1 or P2.
As a result, the issue of discovering two disjoint long pathways is NP-complete.

Conclusion: Because the problem is NP-hard and NP-complete in NP.