13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Up to a length of log n there is a polynomial time algorithm if that helps. And also on DAGs you don't need to use dp unless you want to, you can also assign weights -1 to the edges and run a shortest path algorithm. $\endgroup$ – Nobody Jun 21 '19 at 20:07
  • 1
    $\begingroup$ Well it may be interesting,what is that polynomial time algorithm? $\endgroup$ – Evren Guney Jun 22 '19 at 17:46
  • $\begingroup$ There is a deterministic one that I don't know and a randomized one that works as follows: To find a path of length k, randomly color the graph with k colors. Then for i from 1 to k calculate for each vertex whether there exists a path with unique colors (i.e. no two vertices have same color) of length i. If there exists a path of length k, then the expected number of repetitions until you find it is exponential in k, but because we bound k by $\log|V|$ , it's still polynomial in $|V|$ and $|E|$. $\endgroup$ – Nobody Jun 22 '19 at 18:07
13
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Note that there are other possibilities. I.e. NP \subseteq BPP which would not imply P = NP but give you an efficient randomized method. $\endgroup$ – Fleeep Jun 21 '19 at 9:29
9
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Addon: for undirected graphs, I believe KaLP is one of the most efficient approaches to find longest paths. $\endgroup$ – Marcus Ritt Jun 21 '19 at 23:59
8
$\begingroup$

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 coding1

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 decomposition2. 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$.3

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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