2
$\begingroup$

Given a directed graph $G$ and two vertices $u$ and $w$, how can we find a simple cycle that goes through $u$ and $w$?

One can try putting together paths from $u$ to $w$ and $w$ to $u$ — but these might have edges or nodes in common, even if they are chosen to be shortest paths.

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts? We're not here to solve your exercises for you. Rather, we're here to help you solve them on your own. Therefore we need to know what exactly you tried and where you got stuck. $\endgroup$ – Yuval Filmus Mar 14 '16 at 19:55
  • $\begingroup$ Well, one can try putting together paths from u to w and w to u -- but these might have edges or nodes in common, even if they are chosen to be shortest paths... $\endgroup$ – Michael R Mar 14 '16 at 20:47
  • $\begingroup$ Not reading any particular textbook or learning any concepts DW -- just thought of the question on my own and didn't know how to answer. $\endgroup$ – Michael R Mar 14 '16 at 21:51
2
$\begingroup$

The decision version of your problem (deciding whether such a cycle exists) is NP-complete. See Proposition 9.2.1(P3) on page 477 (495) in Digraphs – Theory, Algorithms and Applications by Bang-Jensen and Gutin.

$\endgroup$
  • $\begingroup$ Thank you! This is so surprising to me. Perhaps this is because I have no background in computer science (I have an undergrad math degree from a couple of decades ago), but still I never would have guessed this problem isn't poly time. $\endgroup$ – Michael R Mar 14 '16 at 23:40
  • $\begingroup$ Note that this problem is not hard in undirected graphs. It can be solved by a DFS. $\endgroup$ – adrianN Mar 15 '16 at 8:32

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.