<p>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\}) &amp; v\neq s\\
0 &amp; \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\})$.</p>

CC BY-SA 3.0
2011-04-13T09:50:44.947Z
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$)
jmacedo
CC BY-SA 3.0
2011-04-13T10:16:59.777Z
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)$.
Marcus Ritt
CC BY-SA 3.0
2011-04-13T11:57:42.130Z
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)$
jmacedo
CC BY-SA 3.0
2011-04-13T13:47:45.187Z
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 http://www.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)$.
Marcus Ritt
CC BY-SA 3.0
2011-04-13T21:11:46.900Z
@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..
jmacedo
CC BY-SA 3.0
2011-04-13T21:23:23.067Z
...the coordenates where is the information of the invocation of the function call $ L(w,S\cup\{w\})$ that did maximize $d_{vw}+L(w,S\cup\{w\}) $ , and the vertex $w$ ?
jmacedo
CC BY-SA 3.0
2011-04-15T00:10:49.963Z
@joxnas I think you should be able to work this out. Maybe the discussion in http://www.dreamincode.net/forums/topic/190644-travelling-salesman-problem-with-dynamic-programming provides some inspiration.
Marcus Ritt
CC BY-SA 3.0
2011-04-12T23:12:55.497Z
2011-04-13T00:26:20.080Z
2011-04-13T00:26:20.080Z
Marcus Ritt
<p><a href="http://dx.doi.org/10.1016/j.ipl.2008.11.004">Williams (2009)</a> [<a href="http://arxiv.org/abs/0807.3026">arXiv version</a>] 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.</p>

CC BY-SA 3.0
2015-09-17T15:28:44.297Z
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. http://epubs.siam.org/doi/abs/10.1137/S0097539704445366?journalCode=smjcat
Chandra Chekuri
CC BY-SA 3.0
2011-04-12T21:07:10.830Z
2011-04-12T21:07:10.830Z
Serge Gaspers
<p>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</p>

CC BY-SA 3.0
2011-04-13T10:50:23.280Z
Is the problem not changed at all due to the sparsity of the graph?
Niel de Beaudrap
CC BY-SA 3.0
2011-04-12T20:36:39.023Z
2011-04-12T20:36:39.023Z
Suresh Venkat
<p>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 :</p>

<p><a href="http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path" rel="nofollow">http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path</a></p>

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

<p>Nathann</p>

CC BY-SA 3.0
2011-11-13T07:47:25.730Z
where is source code for this implementation?
user997704
CC BY-SA 3.0
2011-04-12T21:17:35.867Z
2011-04-12T21:17:35.867Z
Nathann Cohen
<p>I'm looking for an algorithm to find the longest path between two nodes in a bidirectional, unweighted, cyclic graph.</p>

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

<p>Would someone point me a to a good one (site or explain)?</p>

<p>The graph will be sparse.</p>

<p>Thanks for any help!</p>

CC BY-SA 3.0
2011-04-12T20:37:59.520Z
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.
Suresh Venkat
<ds.algorithms><graph-algorithms>
Finding the longest path between two nodes in a bidirectional unweighted graph
jmacedo
# Finding the longest path between two nodes in a bidirectional unweighted graph

(Asked by: username_0 on 2011-04-12)

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!

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 4 answers

### Answer by username_2 on 2011-04-12. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: 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$)  
> **username_2**: 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)$.  
> **username_0**: 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)$  
> **username_2**: 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 http://www.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)$.  
> **username_0**: @username_2 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..  
> **username_0**: ...the coordenates where is the information of the invocation of the function call $ L(w,S\cup\{w\})$ that did maximize $d_{vw}+L(w,S\cup\{w\}) $ , and the vertex $w$ ?  
> **username_2**: @joxnas I think you should be able to work this out. Maybe the discussion in http://www.dreamincode.net/forums/topic/190644-travelling-salesman-problem-with-dynamic-programming provides some inspiration.  

---

### Answer by username_3 on 2011-04-12. Score: 6

[Williams (2009)](http://dx.doi.org/10.1016/j.ipl.2008.11.004) [[arXiv version](http://arxiv.org/abs/0807.3026)] 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.

> **Comments:**
> **username_4**: 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. http://epubs.siam.org/doi/abs/10.1137/S0097539704445366?journalCode=smjcat  

---

### Answer by username_1 on 2011-04-12. Score: 4

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

> **Comments:**
> **username_5**: Is the problem not changed at all due to the sparsity of the graph?  

---

### Answer by username_6 on 2011-04-12. Score: 2

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

> **Comments:**
> **username_7**: where is source code for this implementation?  

---

