Is realization of unit disk graphs hard?

Question

It is known that recognizing a unit disk graph is NP-hard [1].

However, the paper does not mention how hard the realization problem is.

I have looked up several references [2][3][4]. None of the papers answer whether the following problem is NP-hard:

Given a unit disk graph $G = (V,E)$, find a configuration of a set $\mathcal{D}$ of disks, such that the intersection graph $G(\mathcal{D})$ of $\mathcal{D}$ is isomorphic to $G$.

The difference between this problem and the recognition problem is that the input of this problem is guaranteed to be a unit disk.

Is there any study that shows the complexity of the above problem? I expect it to be NP-hard, but I am yet to find a full proof.

Answer 1

One of the complications here is that there is no natural "decision variant" of this problem, since this isn't an optimization problem. (and the problem "given an UDG, is there a realization?" is trivial)

Since reductions between decision problems tend to be better studied, one option is to make it an optimisation problem in a chosen parameter. Even though you don't care about that value, you can use binary search on the optimisation problem to solve the realisation problem. Hence, the realisation problem is not much easier than the opt. problem, so showing the opt. problem is hard suffices.

The question then of course is what parameter to choose. Perhaps the problem "Given an UDG, find a realisation with minimum/maximum sum of edge lengths" would be suitable. It seems related to the problem that Aspnes et al. [1] show to be NP-hard.

---

[1]: ASPNES, James, et al. A theory of network localization. IEEE Transactions on Mobile Computing, 2006, 5.12: 1663-1678.

Answer 2

If there would be a polynomial time algorithm for your problem, it could be used to solve the NP-hard recognition problem in polynomial time by just giving the input to it and checking if its output is correct. Therefore the problem you pose is NP-hard in the sense that if it admits polynomial time algorithm, then P=NP.

(Here we assume that the input is some well-known encoding of a graph, and therefore the restriction that the input must be an unit disk graph doesn't really make the problem at all easier. Maybe there could be some other encodings in which only unit disk graphs could be represented, but formulating them would be another topic.)

---

Edit: I'll try to formalize the question and the answer more:

Formalization of the question: Is there a Turing machine $M$ and a polynomial $p(n)$, such that if the input of $M$ is a unit disk graph $G$ with $n$ vertices encoded as an adjacency matrix, then $M$ terminates in at most $p(n)$ steps, and outputs an unit disk configuration of $G$? In particular, the machine $M$ is allowed to have undefined behavior if the input is not an unit disk graph encoded as adjacency matrix.

Answer: Suppose that there is such Turing machine $M$ and polynomial $p(n)$. Now, we can solve unit disk recognition problem in polynomial time as follows: Given a graph $G$ with $n$ vertices, run $M$ with $G$ as input for $p(n)$ steps. If $M$ does not terminate in $p(n)$ steps, output NO. If $M$ terminates, test if the output of $M$ is an unit disk configuration of $G$. If it is, output YES and otherwise NO. Now we have solved an NP-hard problem in polynomial time, so we have a contradiction if we assume $P \neq NP$.