2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you studied [1] to see if its ideas can be useful? It looks like [1] reduces SAT to recognition. Have you studied that reduction? Does it reduce "given a satisfiable 3CNF formula, find a satisfying assignment" to the realization problem? $\endgroup$ – D.W.♦ Jun 25 '20 at 5:24
  • $\begingroup$ @Discretelizard can you please write your comments as an answer so that I can accept it? $\endgroup$ – padawan Oct 6 '20 at 21:11
  • $\begingroup$ @padawan I put my comments in answer. Sorry for the delay, I wanted to check whether the other answer made my comments obsolete. (I think my answer is still useful, because the other answer doesn't seem to lead to a reduction) $\endgroup$ – Discrete lizard♦ Oct 11 '20 at 9:19
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

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$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ What if we know that the input is a unit disk graph? $\endgroup$ – padawan Oct 7 '20 at 18:11
  • $\begingroup$ The point is that it is difficult to formalize what "we know that the input is a unit disk graph" means. The input is a sequence of 0s and 1s, and if we had some oracle who could tell if it is valid, then the oracle could be used to solve this NP-hard problem. $\endgroup$ – Laakeri Oct 8 '20 at 3:35
  • 1
    $\begingroup$ What if the algorithm is only polynomial under the condition that the input is an unit disk graph? For example, suppose that for some graphs that are not unit disk graphs, the algorithm does not even terminate? $\endgroup$ – Discrete lizard♦ Oct 8 '20 at 14:07
  • $\begingroup$ You could run the algorithm for "polynomial number" of steps, and if it does not terminate, then terminate with a negative answer. Note that we will know an upper bound for the polynomial because we supposedly have a proof that the algorithm works in polynomial time under the condition that the input is valid. $\endgroup$ – Laakeri Oct 9 '20 at 5:35
  • $\begingroup$ @Laakeri I guess that might work, but can we consider the algorithm to be an oracle if we also inspect how long it has to run? That is, do we still have a Turing reduction? $\endgroup$ – Discrete lizard♦ Oct 11 '20 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.