  Several works have recently investigated the parameterized complexity of data
completion problems, motivated by their applications in machine learning, and
clustering in particular. Interestingly, these problems can be equivalently
formulated as classical graph problems on induced subgraphs of powers of
partially-defined hypercubes.
  In this paper, we follow up on this recent direction by investigating the
Independent Set problem on this graph class, which has been studied in the data
science setting under the name Diversity. We obtain a comprehensive picture of
the problem's parameterized complexity and establish its fixed-parameter
tractability w.r.t. the solution size plus the power of the hypercube.
  Given that several such FO-definable problems have been shown to be
fixed-parameter tractable on the considered graph class, one may ask whether
fixed-parameter tractability could be extended to capture all FO-definable
problems. We answer this question in the negative by showing that FO model
checking on induced subgraphs of hypercubes is as difficult as FO model
checking on general graphs.
