  Rydberg atom arrays are among the leading contenders for the demonstration of
quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi
et al., Science 376, 1209 (2022)] we study the maximum independent set problem
on unit-disk graphs with a broader range of classical solvers beyond the scope
of the original paper. We carry out extensive numerical studies and assess
problem hardness, using both exact and heuristic algorithms. We find that
quasi-planar instances with Union-Jack-like connectivity can be solved to
optimality for up to thousands of nodes within minutes, with both custom and
generic commercial solvers on commodity hardware, without any instance-specific
fine-tuning. We also perform a scaling analysis, showing that by relaxing the
constraints on the classical simulated annealing algorithms considered in Ebadi
et al., our implementation is competitive with the quantum algorithms.
Conversely, instances with larger connectivity or less structure are shown to
display a time-to-solution potentially orders of magnitudes larger. Based on
these results we propose protocols to systematically tune problem hardness,
motivating experiments with Rydberg atom arrays on instances orders of
magnitude harder (for established classical solvers) than previously studied.
