Detecting wheels

Emilie Diot (1) , Sébastien Tavenas (2) , Nicolas Trotignon (3, 4)

1 Service de Médecine Interne
2 MPII - Max-Planck-Institut für Informatik
3 LIP - Laboratoire de l'Informatique du Parallélisme
4 MC2 - Modèles de calcul, Complexité, Combinatoire

A \emph{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.

Domaines: Mathématique discrète [cs.DM]

Emilie Diot, Sébastien Tavenas, Nicolas Trotignon. Detecting wheels. Applicable Analysis and Discrete Mathematics, 2014, 8 (1), ⟨10.2298/AADM131128023D⟩. ⟨hal-01230785⟩