1
$\begingroup$

The problem of finding the longest path in a graph is known to be not be possible in polynomial time, that I am aware of. I am also aware that using DFS or BFS can give the shortest distance between a given origin and destination in a graph. Is it possible to find a longest path from a source vertex to a destination vertex in polynomial time?

$\endgroup$
1
  • $\begingroup$ Note to any readers: it is important that the longest path problem asks for the longest simple path, i.e. the path does not repeat vertices. If the question is to find the longest path which may repeat vertices, then the problem can be solved in polynomial time with dynamic programming. $\endgroup$ Commented May 6, 2020 at 2:13

1 Answer 1

2
$\begingroup$

The longest-path problem is $\mathsf{NP}$-hard even when a source vertex $s$ and a target vertex $t$ are specified. To see this, you can reduce an instance of (the decision version of) longest path on a graph $G =(V,E)$ with no source/destination specified to (the decision version of) this variant by:

  • Adding to $G$ a new path $\langle u_0, \dots, u_n \rangle$ of length $n = |V|$, and connecting $u_n$ to each of the vertices $v \in V$ via the edge $(u_n, v)$; and

  • Adding to $G$ a new path $\langle z_0, \dots, z_n \rangle$ length $n$, and connecting each of the vertices $v \in V$ to $z_0$ via the edge $(v, z_0)$.

Call the resulting graph $G'$. It is easy to see that there is path of length $k$ in $G$ if and only if there is path from $u_0$ to $z_n$ of length $2n + k$ in $G'$.

This shows that, if $\mathsf{P} \neq \mathsf{NP}$ your variant does not admit any polynomial-time algorithm.

If $\mathsf{P} = \mathsf{NP}$, then there is a polynomial time algorithm for the decision version of longest path (given a graph $G$, two vertices $s$ and $t$, and an integer $k$, decide whether there is a path from $s$ to $t$ in $G$ of length at least $k$), which is $\mathsf{NP}$-Complete.

Your version of longest path can then solved in polynomial time by first finding the length $k$ of a longest path $P$ and then recursively guessing the next vertex of $P$: delete $s$ from $G$ and check, for every neighbor $u$ of $s$, whether there exists a path $P'$ from $u$ to $t$ in $G-s$. When you find a $u$ for which the answer is affirmative, solve the problem recursively on $G-s$ to find $P'$ and construct $P$ as $s \circ P'$, where $\circ$ denotes concatenation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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