<p>See <a href="http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf">http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf</a>.</p>

CC BY-SA 3.0
2012-01-10T15:06:41.477Z
Hey, that's a very cool paper! Thanks for the link.
zotachidil
CC BY-SA 3.0
2012-01-10T16:59:26.843Z
extra points for the neat decoration on the front page. How did you do that ?
Suresh Venkat
CC BY-SA 3.0
2012-01-10T17:40:50.940Z
is it obvious that an algorithm for finding a cycle works for a path?
didest
CC BY-SA 3.0
2012-01-10T17:54:04.630Z
@Diego: Add a specified edge between the two vertices which you want to be endpoints of the path.
Andreas Björklund
CC BY-SA 3.0
2012-01-10T14:11:57.093Z
2012-01-10T14:11:57.093Z
Andreas Björklund
<p>For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing
all elements of $S$. What if we require the path to be as short as possible ?</p>

<ds.algorithms><graph-algorithms><time-complexity>
Fastest known algorithm for finding simple paths through given set of vertices
shuaoT
# Fastest known algorithm for finding simple paths through given set of vertices

(Asked by: username_0 on 2012-01-10)

For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing
all elements of $S$. What if we require the path to be as short as possible ?

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

---

## 1 answers

### Answer by username_1 on 2012-01-10. Score: 17 | Accepted answer

See <http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf>.

> **Comments:**
> **username_2**: Hey, that's a very cool paper! Thanks for the link.  
> **username_3**: extra points for the neat decoration on the front page. How did you do that ?  
> **username_4**: is it obvious that an algorithm for finding a cycle works for a path?  
> **username_1**: @Diego: Add a specified edge between the two vertices which you want to be endpoints of the path.  

---

