Are there any efficient algorithms to solve the longest path problem in networks with cycles?

Question

I have a directed social network and as a preprocessing step I need to calculate the longest path lengths for each node. Longest path problem is NP-hard as far as I know but I've seen dynamic programming methods for DAGs. Is there such a method for general networks with cycles? All arc weights are one.

Answer 1

There is no theoretically efficient method, unless P=NP.

The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each vertex exactly once. This problem is NP-complete (see link).

If you could determine the longest path efficiently, you could do so for every starting point and ending point. If for any pair the length is equal to the number of points minus one, you have proven that there exists an Hamiltonian path. If not, then there is no Hamiltonian path.

It follows that determining the longest path must be NP-hard.

Answer 2

As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $\sf{P=NP}$.

Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy \begin{align*} C(s,t,V)= \begin{cases} \max\limits_{u\in N^{-}(t)\setminus V} C(s,u,V\cup\{t\})+d_{ut}, & \text{if $s\neq t$ and $N^{-}(t)\setminus V\neq \emptyset$},\\ -\infty, & \text{if $s\neq t$ and $N^{-}(t)\setminus V=\emptyset$},\\ 0, & \text{if $s=t$}, \end{cases} \end{align*} where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_{uv}$ is the distance between $u$ and $v$. Computing $C$ for fixed $s$ takes time $O(n^22^n)$ and space $O(n2^n)$ and $C(s,t,\emptyset)$ gives the longest path between $s$ and $t$.

Answer 3

As other answers have already noted, this problem is NP-hard. That, however, is not the end of the story. The longest path problem has some positive algorithmic results in the context of parametrized algorithms.

The main idea is that even though the problem may be NP-hard in general, we can consider a parameter of the input $k$ and try to develop algorithms that are efficient when $k$ is small. In particular, a problem is considered fixed parameter tractable (FPT) w.r.t. parameter $k$ if there is an $O(f(k)\cdot \mathrm{poly}(n))$ time algorithm that solve the problem, for some computable function $f$.

I will discuss two of the techniques, which I mostly took from the textbook Cygan, et al. Parameterized algorithms. Vol. 4. No. 8. Cham: Springer, 2015.. (I highly recommend this book for anyone interested in parametrized algorithms and analysis!)

Color coding¹

For this technique, we will consider the $k$-path problem, where we ask if there is a simple path of length $k$. This is the longest path problem in disguise: if we know the longest path is at most of length $x$, we can do a binary search and only add a $\log x$ factor.

One reason why longest path is hard is because we want a simple path. It is a bit easier to decide whether there is a walk of length $k$. So we want to get an efficient way to look only at simple paths. I will quote the main trick directly from the book:

Color the vertices uniformly at random from $\{1,\ldots,k\}$, and find a path on $k$ vertices, if it exists, whose all colors are pairwise distinct.

We call a path with pairwise distinct colors colorful. Note that a colorful path must be simple. What remains to be shown is whether it is likely for a simple path of length $k$ to be colorful. It turns out that this happens with probability at least $e^{-k}$. In the end, we get an $(2e)^k\mathrm{poly}(n)$ time algorithm with one-sided constant error probability, where the $2^k$ factor is for checking whether there is a colorful $k$-path. A more involved algorithm can lower the base of the exponent somewhat, to get an $4^{k+o(k)}\mathrm{poly}(n)$-time algorithm.

There are methods to derandomize this technique, but I will not discuss them here.

Treewidth

Many graph problems are easy on trees, longest path included. The notion of treewidth is used to extend these techniques to more general graphs. We can group vertices of our graph $G$ into 'bags' and then construct a graph $G'$ with the bags as vertices and an edge between bags if some vertices in the bags are connected in the original graph $G$. If $G'$ is a tree, this is called a tree decomposition². The treewidth of a graph $G$ is the minimum $k$ such that there is a tree decomposition where every bag has size at most $k$.³

Of course, it is not immediately clear that treewidth is less than $O(n)$ for an arbitrary graph. The treewidth of a graph can be found in time FPT wrt to the treewidth as a parameter. Additionally, cycles have treewidth $2$, $t\times t$ grids have treewidth $O(t)$, and more generally planar graphs have treewidth $O(\sqrt{n})$.

To get an algorithm that is FPT in the treewidth, the main trick is that dynamic programming is as easy on a tree decomposition of bounded size as on ordinary trees. With this technique, we get an $k^{O(k)}\cdot n$ time algorithm. This is pretty bad if the treewidth of your graph is not small, but if it happens to be bounded by a constant, this is a linear time algorithm!

---

_{1: This is the technique mentioned by @Nobody in the comments .
2,3: This is not completely correct, but it should give you an idea.}