Abstract:
We study the complexity of recognizing $A$-distance graphs in $\mathbb{R}^d$ and prove that for all finite sets $A$ such that any two elements of the set differ by a factor $\geqslant 2$, the recognition problem for $A$-distance graphs is $\mathrm{NP}$-hard for any $d \geqslant 3$.