Proving Longest Path Belongs to NP & Reducing Hamiltonian Path

[evinda]

Hello! (Smile)

Longest path
We have a graph $G=(V,E)$, lengths $l(e) \in \mathbb{Z}^{+}$ for each $e \in E$, a positive integer $K$ and two nodes $s,t \in V$.

The question is if there is a simple path in $G$ from $s$ to $t$ of length at least $K$.

• Show that the problem Longest Path belongs to NP.
• Show that the problem Longest Path is NP-complete, reducing Hamiltonian Path to it.
• Show that if the graph is directed and acyclic then the problem can be solved in time $O(|V|+|E|)$.

Could you give me a hint how we could show that the problem belongs to NP? Also, how can we reduce a problem to an other, in order to show that the latter is NP-complete?

 

[alyafey22]

To prove that it is NP we need to construct a non-deterministic algorithm that solves the problem in polynomial time.
The idea is to construct a path between (s,t) and check if it is at least k.

 

[evinda]

To prove that it is NP we need to construct a non-deterministic algorithm that solves the problem in polynomial time.
The idea is to construct a path between (s,t) and check if it is at least k.

So could we justify that the problem is in NP as follows?

If we construct a simple path between (s,t) we can easily check that it length is at least k, by simply computing the sum of lengths of all edges in it. Thus, it is in NP.Also, suppose that we have a problem A and a problem B and it is known that B is NP-complete. If we want to show that A is also NP-complete, do we change the data of A in that way so that we have the same problem as the problem B and so we deduce that A is also NP-complete? Or am I wrong?

 

[alyafey22]

So could we justify that the problem is in NP as follows?

If we construct a simple path between (s,t) we can easily check that it length is at least k, by simply computing the sum of lengths of all edges in it. Thus, it is in NP.

To prove that a problem belongs to the class NP we need to do the two steps guessing and verification. Then we have to show that this can be done in polynomial time. It is clear that the verification can be done in polynomial time by computing the length of the path. You need to do the guessing step by constructing an algorithm that has a complexity in P.

Also, suppose that we have a problem A and a problem B and it is known that B is NP-complete. If we want to show that A is also NP-complete, do we change the data of A in that way so that we have the same problem as the problem B and so we deduce that A is also NP-complete? Or am I wrong?

Reducing B to A means that given an instance in B we can solve A iff we solve B. It is actually the opposite to what you said. We need to construct an instance of A from B. For example, the Hamiltonian path problem deals with graphs with unweighted edges while the longest path problem deals with graphs with weighted edges.

 

[evinda]

To prove that a problem belongs to the class NP we need to do the two steps guessing and verification. Then we have to show that this can be done in polynomial time. It is clear that the verification can be done in polynomial time by computing the length of the path. You need to do the guessing step by constructing an algorithm that has a complexity in P.

So at the guessing step, given a simple path between (s,t), do we have to write an algorithm that computes the sum of lengths of all edges in it and then at the verification we find the time complexity of the algorithm? Or have I understood it wrong? (Thinking)

Reducing B to A means that given an instance in B we can solve A iff we solve B. It is actually the opposite to what you said. We need to construct an instance of A from B. For example, the Hamiltonian path problem deals with graphs with unweighted edges while the longest path problem deals with graphs with weighted edges.

I see.. but I haven't understood how we could do this... Could you explain it further to me?

 

[alyafey22]

So at the guessing step, given a simple path between (s,t), do we have to write an algorithm that computes the sum of lengths of all edges in it and then at the verification we find the time complexity of the algorithm? Or have I understood it wrong? (Thinking)

No. In the guessing step you construct a solution for the problem. Given an instance of the Longest path problem, we construct a solution for it.

I see.. but I haven't understood how we could do this... Could you explain it further to me?

Let us focus on solving the first part,first.

 

[evinda]

No. In the guessing step you construct a solution for the problem. Given an instance of the Longest path problem, we construct a solution for it.

Could we say for example the following?A non-deterministic Turing machine can first "guess" which two nodes $s,t$ are the initial and final node respectively of the longest path and then verify that the path from $s$ to $t$ is simple and has a length of $k$ in $O(E)$ steps.

 

[alyafey22]

Given a graph G with n vertices and (s,t) we randomly choose (n-2) non-repeated vertices. Hence we will get n vertices with the first vertex s and the last vertex t. Now we need to verify the conditions for the Longest path problem.

 

[evinda]

Given a graph G with n vertices and (s,t) we randomly choose (n-2) non-repeated vertices. Hence we will get n vertices with the first vertex s and the last vertex t. Now we need to verify the conditions for the Longest path problem.

So don't we have to say anything about the length of the path? (Thinking)

 

[alyafey22]

So don't we have to say anything about the length of the path? (Thinking)

This is the guessing step. Now we need to do the verification step which has to prove whether the solution generated from the guessing step is correct. How do you think we can do that ?

 

[evinda]

So could we use the following as the guessing and verification step?

Given a graph $G$ with $n$ vertices and $(s,t)$, a non-deterministic Turing machine first guesses which $(n-2)$ non-repeated vertices form the longest path of length $n$, of which the first vertex is $s$ and the last is $t$ and then it verifies that the path from $s$ to $t$ is simple and that its length is at least $K$ in $O(E)$ steps.

In addition, could we show that the problem Longest Path is NP-complete, reducing Hamiltonian Path to it as follows?Let $G_1=(V,E)$, lengths $m(e)=1$ for each $e \in E$ a random instance of the Hamiltonian path problem.
We can construct an instance of the Longest path problem in polynomial time as follows:

$G_1$ corresponds to the graph $G$, the lengths $m(e)$ correspond to the lengths $l(e) \geq 1$ and $|E|$ corresponds to $K$.

The problem Hamiltonian path has a solution iff at $G_1$ there is a simple path of length $|E|=|V|-1$, i.e. $\sum m=|E|=|V|-1$.
Since $l(e) \geq m \Rightarrow \sum l(e) \geq \sum m=|E|=|V|-1$.

So we have that the problem Hamiltonian path has a solution iff at $G$ there is a simle path of length at least $K$.

Thus, the instance of the problem Longest path has a solution iff the initial instance of the problem Hamiltonian path has a solution.

Therefore, the problem Longest path is NP-complete.Or could I improve something?

 

[Evgeny.Makarov]

Given a graph $G$ with $n$ vertices and $(s,t)$, a non-deterministic Turing machine first guesses which $(n-2)$ non-repeated vertices form the longest path of length $n$, of which the first vertex is $s$ and the last is $t$ and then it verifies that the path from $s$ to $t$ is simple and that its length is at least $K$ in $O(E)$ steps.

The longest path from $s$ to $t$ does not have to consist of $n$ vertices. It may consist of just 2 vertices.

In addition, could we show that the problem Longest Path is NP-complete, reducing Hamiltonian Path to it as follows?

Let $G_1=(V,E)$, lengths $m(e)=1$ for each $e \in E$ a random instance of the Hamiltonian path problem.

Don't use the word "random". It has a technical meaning. You may say, "an instance" or "an arbitrary instance". Also, the Hamiltonian path problem does not include function $m$.

We can construct an instance of the Longest path problem in polynomial time as follows:

$G_1$ corresponds to the graph $G$, the lengths $m(e)$ correspond to the lengths $l(e) \geq 1$ and $|E|$ corresponds to $K$.

The meaning of "corresponds" is not clear. You should describe how you construct $G$, $m$ and $K$. For example, "… and let $K=|E|$".

The problem Hamiltonian path has a solution iff at $G_1$ there is a simple path of length $|E|=|V|-1$

Why do you think that $|E|=|V|-1$ where $E$ is the set of edges in the original graph?

 

[evinda]

The longest path from $s$ to $t$ does not have to consist of $n$ vertices. It may consist of just 2 vertices.

Could we justify that the problem is in NP like that?

A non-deterministic Turing machine first "guesses" the path and then it verifies that this path is simple and its length is at least $K$ in $O(E)$ steps. So the problem Longest path is in NP.

Don't use the word "random". It has a technical meaning. You may say, "an instance" or "an arbitrary instance". Also, the Hamiltonian path problem does not include function $m$.

Ok.. (Smile)

The meaning of "corresponds" is not clear. You should describe how you construct $G$, $m$ and $K$. For example, "… and let $K=|E|$".

So could we start as follows?Let $G_1=(V_1,E_1)$ an arbitrary instance of the Hamiltonian path problem.

We can construct an instance of the Longest path problem in polynomial time as follows:

Let $G_1$ be the graph $G$, $l(e)=1$ for each $e \in E$ and $|E_1|=K$.

Why do you think that $|E|=|V|-1$ where $E$ is the set of edges in the original graph?

Oh, I am sorry... (Blush)
So could we continue as follows?

The problem Hamiltonian path has a solution iff at $G_1$ there is a simple path of length $|E_1|=|V_1|-1$.

So we have that the problem Hamiltonian path has a solution iff at $G$ there is a simple path of length $K$.

Thus, the instance of the problem Longest path has a solution iff the initial instance of the problem Hamiltonian path has a solution.

Therefore, the problem Longest path is NP-complete.

 

[Evgeny.Makarov]

Could we justify that the problem is in NP like that?

A non-deterministic Turing machine first "guesses" the path and then it verifies that this path is simple and its length is at least $K$ in $O(E)$ steps. So the problem Longest path is in NP.

This is OK.

Let $G_1=(V_1,E_1)$ an arbitrary instance of the Hamiltonian path problem.

We can construct an instance of the Longest path problem in polynomial time as follows:

Let $G_1$ be the graph $G$, $l(e)=1$ for each $e \in E$ and $|E_1|=K$.

Usually one says, "Let $x$ be $y$" if $y$ is a known object and $x$ is a new name for it. So it should be, "Let $G$ be $G_1$, $l(e)=1$ and $K=|E_1|$.

So could we continue as follows?

The problem Hamiltonian path has a solution iff at $G_1$ there is a simple path of length $|E_1|=|V_1|-1$.

The Hamiltonian path problem is a set of graphs with a "yes" or "no" answers associated with each graph. It is not clear what you mean by "the Hamiltonian path problem has a solution". Probably you are saying the definition: $G_1$ has a Hamiltonian path iff there is a simple path of length $|V_1|-1$. I am still not sure why $|E_1|=|V_1|-1$. The number of edges in the Hamiltonian path is, of course, $|V_1|-1$, but the number of all edges in $G_1$ can be different.

So $K$ should be set to $|V_1|-1$.

So we have that the problem Hamiltonian path has a solution iff at $G$ there is a simple path of length $K$.

Again, I don't think the phrase "the problem has a solution" is correct. Lewis & Papadimitriou's book uses the phrase "$G$ is a 'yes' instance of the Hamiltonian path problem", or just "$G$ has a Hamiltonian path".

 

[evinda]

This is OK.

Nice.. (Happy)

Usually one says, "Let $x$ be $y$" if $y$ is a known object and $x$ is a new name for it. So it should be, "Let $G$ be $G_1$, $l(e)=1$ and $K=|E_1|$.

The Hamiltonian path problem is a set of graphs with a "yes" or "no" answers associated with each graph. It is not clear what you mean by "the Hamiltonian path problem has a solution". Probably you are saying the definition: $G_1$ has a Hamiltonian path iff there is a simple path of length $|V_1|-1$. I am still not sure why $|E_1|=|V_1|-1$. The number of edges in the Hamiltonian path is, of course, $|V_1|-1$, but the number of all edges in $G_1$ can be different.

So $K$ should be set to $|V_1|-1$.

Again, I don't think the phrase "the problem has a solution" is correct. Lewis & Papadimitriou's book uses the phrase "$G$ is a 'yes' instance of the Hamiltonian path problem", or just "$G$ has a Hamiltonian path".

So in total, can we say the following?

Let $G_1=(V_1,E_1)$ an arbitrary instance of the Hamiltonian path problem.

We can construct an instance of the Longest path problem in polynomial time as follows:

Let $G$ be the graph $G_1$, $l(e)=1$ for each $e \in E$ and $K=|V_1|-1$.

$G_1$ has a Hamiltonian path iff there is a simple path of length $|V_1|-1$.

So we have that $G_1$ has a Hamiltonian path iff at $G$ there is a simple path of length $K$.

Thus, the instance of the problem Longest path has a solution iff the initial instance of the problem Hamiltonian path has a solution.

Therefore, the problem Longest path is NP-complete.

 

[Evgeny.Makarov]

It's OK.

 

[evinda]

It's OK.

Nice... :)I have tried to write an algorithm that solves the problem in $O(|V|+|E|)$ time, given that the graph is directed and acyclic.

Longest_path(G,s){
1.   compute a topological sorting {v_0, v_1,..., v_(|V|-1)} // v_0=s
2.   D[s]<-0
3.   for each vertex u!=s{
4.        D[u]<- -∞
5.        pi[u]<-null
6.   }
7.   for i=0 to |V|-1{
8.        for each edge (v_i,u) outgoing from v_i {
9.             if D[v_i]+w(v_i,u)>D[u]{
10.                D[u]<- D[v_i]+w(v_i,u)
11.                pi[u]<-v_i
12.             }
13.       }
14.  }
15.}

The time complexity of the topological sorting is $O(|V|+|E|)$.
The first for-loop at the lines 3-6 is executed $O(|V|)$ times.
The outer for-loop that begins at the line 7 is executed $|V|-1-0+1=|V|$ times.
The inner for-loop that begins at the line 8 is executed $\sum{\text{ outgoing edges }}=|E| $ times.
The commands at the lines 9, 10, 1 require constant time.
So the time complexity of the algorithm is $O(|V|+|E|)+O(|V|)+O(|E|)+O(1)=O(|V|+|E|)$ time.
Could you tell me if my idea is right? (Thinking)

 

[Evgeny.Makarov]

I agree except that s does not have to be v_0.

 

[evinda]

I agree except that s does not have to be v_0.

Do you mean that we can give at the algorithm any vertex we want as an argument and replace at lines 2,3 $s$ with $v_0$?
Or have I understood it wrong?

 

[Evgeny.Makarov]

Do you mean that we can give at the algorithm any vertex we want as an argument

Yes. The problem statement says that $s,t\in V$ and does not impose any restrictions on them. In particular, there is no restriction that $s$ has only outgoing edges (which is necessary for $v_0$).

and replace at lines 2,3 $s$ with $v_0$?

No. If you wrote the algorithm in post #17, you should be able to decide whether it should say [m]D <- 0[/m] or [m]D[v_0] <- 0[/m] in line 2.