10
$\begingroup$

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 ?

$\endgroup$
17
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Hey, that's a very cool paper! Thanks for the link. $\endgroup$ – zotachidil Jan 10 '12 at 15:06
  • 2
    $\begingroup$ extra points for the neat decoration on the front page. How did you do that ? $\endgroup$ – Suresh Venkat Jan 10 '12 at 16:59
  • $\begingroup$ is it obvious that an algorithm for finding a cycle works for a path? $\endgroup$ – didest Jan 10 '12 at 17:40
  • 3
    $\begingroup$ @Diego: Add a specified edge between the two vertices which you want to be endpoints of the path. $\endgroup$ – Andreas Björklund Jan 10 '12 at 17:54

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.