The fCyclabilityf completeness conjecture

Let $G$ be a graph, and say that $G$ is cyclable if every set of vertices of the relevant size is contained in a cycle. The problem \textsc{Cyclability} asks, given a graph and an integer, whether the graph has this property.

Cyclability completeness conjecture. The problem \textsc{Cyclability} is $\mathsf{\Pi}_{2}^{\mathrm{P}}$-complete.

The problem is defined directly in $\mathsf{\Pi}_{2}^{\mathrm{P}}$, but the paper notes that it has no proof or evidence of membership in $\mathsf{NP}$. The conjectured completeness therefore concerns the higher complexity class $\mathsf{\Pi}_{2}^{\mathrm{P}}$.