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.
( Read more...Collapse )