A peripheral cycle in an undirected graph is an induced cycle the deletion of which does not separate the remaining graph. For instance, in the graph of a convex polyhedron, the peripheral cycles are exactly the faces of the graph. In any graph, it is possible to find a non-peripheral cycle in linear time, if one exists; see e.g. the Graph Drawing book by Di Battista, Eades, Tamassia, and Tollis, pp. 75–76. Every 3-connected graph has a peripheral cycle, and every 2-connected graph with minimum degree three has a peripheral cycle. So how hard is it to find a peripheral cycle, if one exists, in an arbitrary graph?
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.
Some changes have been made to LiveJournal, and we hope you enjoy them! As we continue to improve the site on a daily basis to make your experience here better and faster, we would greatly appreciate your feedback about these changes. Please let us know what we can do for you!