Longest Path

Input

Graph $G = (V, E)$, length $\ell(e) \in \mathbb{Z}^{+}$ for each $e \in E$, positive integer $K$, specified vertices $s, t \in V$.

Question

Is there a simple path in $G$ from $s$ to $t$ of length $K$ or more, i.e. whose edge lengths sum to at least $K$?

Classes

• NP-complete

Comments

Remains NP-complete if $\ell(e) = 1$ for all $e \in E$, as does the corresponding problem for directed paths in directed graphs. The general problem can be solved in polynomial time for acyclic digraphs, e.g. see (Lawler, 1976). The analogous directed and undirected shortest path problems can be solved for arbitrary graphs in polynomial time (e.g. see (Lawler, 1976)), but are NP-complete if negative lengths are allowed.

Proofs

NP-complete

Transformation from [problem:hamiltonian-path-between-two-vertices].

Reducible from

• [hamiltonian-path-between-two-vertices]

References

• Lawler, E. L. (1976). Combinatorial optimization: networks and matroids. Holt, Rinehart.