  In the past years, many quantum algorithms have been proposed to tackle hard
combinatorial problems. In particular, the Maximum Independent Set (MIS) is a
known NP-hard problem that can be naturally encoded in Rydberg atom arrays. By
representing a graph with an ensemble of neutral atoms one can leverage Rydberg
dynamics to naturally encode the constraints and the solution to MIS. However,
the classes of graphs that can be directly mapped ``vertex-to-atom" on standard
devices with 2D capabilities are currently limited to Unit-Disk graphs. In this
setting, the inherent spatial locality of the graphs can be leveraged by
classical polynomial-time approximation schemes (PTAS) that guarantee an
$\epsilon$-approximate solution. In this work, we build upon recent progress
made for using 3D arrangements of atoms to embed more complex classes of
graphs. We report experimental and theoretical results which represent
important steps towards tackling combinatorial tasks on quantum computers for
which no classical efficient $\varepsilon$-approximation scheme exists.
