Detecting wheels
Emilie Diot, Sébastien Tavenas, Nicolas Trotignon · Applicable Analysis and Discrete Mathematics · 2013
A wheel is a graph made of a cycle of length at least 4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a graph G and whose question is "does G contains a wheel as an induced subgraph" is NP-complete. We also settle the complexity of several similar problems. [LABEX MILYON (ANR-10-LABX-0070) of Universit? de Lyon]