5
$\begingroup$

I'm looking for an algorithm to find the longest path between two nodes in a bidirectional, unweighted, cyclic graph.

The path must not have repeated vertices (otherwise the path would be infinite of course).

Would someone point me a to a good one (site or explain)?

The graph will be sparse.

Thanks for any help!

$\endgroup$
  • 1
    $\begingroup$ I understand the close votes, and I was torn too. But does this maybe come under the category of 'helping someone model a problem' ? In which case it would be worth saving. $\endgroup$ – Suresh Venkat Apr 12 '11 at 20:37
5
$\begingroup$

You can solve your problem in $O(n^2 2^n)$ on a graph with $n$ vertices by dynamic programming. Let $G=(V,E)$ be an undirected graph with edge weights $d_{uv}$. Let $L(v,S)$ be the length of the longest path from some fixed vertex $s$ to vertex $v$, which visits no vertex in $S$. $L$ satisfies $$L(v,S)=\begin{cases} \max_{w\in N(v)\setminus S} d_{vw}+L(w,S\cup\{w\}) & v\neq s\\ 0 & \text{otherwise} \end{cases}\mathrm{,}$$ where $N(v)$ is the set of $v$'s neighbors. (Define the empty $\max$ to be $-\infty$.) Then the longest path between $s$ and $v$ has length $L(v,\{v\})$.

$\endgroup$
  • $\begingroup$ I understand this algorithm, but don't understand why the complexity is $O(n^2{}2^n)$. I was also wondering if this won't compute more then once for the same $v$ and $S$ for example $L(A,\{D,B,C\})$ and $L(A,\{D,C,B\})$ (the order is just to show when you added the vertices to $S$) $\endgroup$ – jmacedo Apr 13 '11 at 9:50
  • 1
    $\begingroup$ You store $L$'s in a table of size $O(n2^n)$ to avoid recomputing them (your examples are the same entry, since $S$ is a set). Each entry can be computed in $O(n)$, so filling the table is $O(n^2 2^n)$. $\endgroup$ – Marcus Ritt Apr 13 '11 at 10:16
  • $\begingroup$ This woud be memoization? I'm sorry not knowing much about dynamical programming. I'm not understanding some things: your algorithm finds the length of the longest path but not the longest path it self. This is no problem to me, i already found out that the maximum path algorithm is analogous to that one. Your saying i need a table to save the returns of the function, so i dont have to repeat the same call. But for my problem, would I need to store the paths? Won't this be too memory heavy? $O(n^2{}2^n)$ $\endgroup$ – jmacedo Apr 13 '11 at 11:57
  • $\begingroup$ You can use memoization or fill the table in a bottom-up manner. You can extract the path by storing the information about the optimal subproblem in the table. Have a look at chapter 6.6 in cs.berkeley.edu/~vazirani/algorithms/chap6.pdf for a similar technique applied to TSP and some more explications. And yes, the approach is not very practical since the table has size $O(n2^n)$. $\endgroup$ – Marcus Ritt Apr 13 '11 at 13:47
  • $\begingroup$ @Marcus Ritt I've read almost the whole chapter specially section 6.6 but missed some things.. The table needs to have $n{}2^n$ because of the possible function arguments, right? ($|\mathcal{P}(S)| = 2^n$) . Still i didn't understand yet these things: given an input $(v,S)$ , how can i know the position in the table where there would be information if it has already been calculated / where do I put the return of a first time calculated input $(v,S)$? Do i need hash tables? Is implicit by the order of function calls? And... the additional info i need to store ,what does it contain? $(i,j)$ of.. $\endgroup$ – jmacedo Apr 13 '11 at 21:11
6
$\begingroup$

Williams (2009) [arXiv version] gives a randomized $2^k poly(n)$ time algorithm finding a path of length at least $k$ in a graph on $n$ vertices. The paper contains pointers to previous deterministic and randomized algorithms. Many of these algorithms can probably be modified to find a $k$-path whose endpoints are given in the input.

$\endgroup$
  • $\begingroup$ I also recommend looking at Gabow's algorithm which finds in polynomial time paths that are longer than log n. However it works only for undirected graphs. epubs.siam.org/doi/abs/10.1137/… $\endgroup$ – Chandra Chekuri Sep 17 '15 at 15:28
4
$\begingroup$

I don't know what "bidirectional" and "cyclic" mean, but I'll assume that they mean "undirected" and "not a DAG or tree". In that case, the problem is called LONGEST-PATH and is NP-hard because it encodes HAMILTONIAN-PATH

$\endgroup$
  • 2
    $\begingroup$ Is the problem not changed at all due to the sparsity of the graph? $\endgroup$ – Niel de Beaudrap Apr 13 '11 at 10:50
2
$\begingroup$

If you are not looking for an algorithm but for an implementation of it and want to solve this problem on an actual graph, this is one of the things Sage (http://sagemath.org/index.html) knows how to do :

http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path

Then again, as it is NP-Hard and not one of the easiest, don't expect too much :-)

Nathann

$\endgroup$
  • $\begingroup$ where is source code for this implementation? $\endgroup$ – user997704 Nov 13 '11 at 7:47

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.