patternMinor
Finding a simple cycle that goes through two vertices
Viewed 0 times
cyclesimplethroughgoestwothatfindingvertices
Problem
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.
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.
Solution
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.
Context
StackExchange Computer Science Q#54470, answer score: 3
Revisions (0)
No revisions yet.