3
$\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$
3
  • 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$ Mar 14, 2016 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, 2016 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, 2016 at 21:51

1 Answer 1

3
$\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$
2
  • $\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, 2016 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, 2016 at 8:32

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.