Is longest-path with a specific source and destination impossible in polynomial time?

Question

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?

Answer 1

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.