6
$\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!

Improve this question
$\endgroup$
1
  • 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
    Commented Apr 12, 2011 at 20:37

4 Answers 4

Reset to default
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\})$.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Apr 13, 2011 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
    Commented Apr 13, 2011 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
    Commented Apr 13, 2011 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
    Commented Apr 13, 2011 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
    Commented Apr 13, 2011 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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Sep 17, 2015 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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Is the problem not changed at all due to the sparsity of the graph? $\endgroup$
    – Niel de Beaudrap
    Commented Apr 13, 2011 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

Improve this answer
$\endgroup$
1
  • $\begingroup$ where is source code for this implementation? $\endgroup$
    – user997704
    Commented Nov 13, 2011 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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