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 ?


1 Answer 1


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

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

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.