Finding peripheral cycles is hard
The answer turns out to be that it's NP-complete. The proof I found uses two reductions, one from graph three-coloring to a problem of finding cycles with forbidden pairs of vertices, and a second one from that to finding peripheral cycles.
( Read more...Collapse )
- 0 comments