![]() If $M$ terminates, test if the output of $M$ is an unit disk configuration of $G$. If $M$ does not terminate in $p(n)$ steps, output NO. 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. 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.Īnswer: Suppose that there is such Turing machine $M$ and polynomial $p(n)$. ![]() Maybe there could be some other encodings in which only unit disk graphs could be represented, but formulating them would be another topic.)Įdit: I'll try to formalize the question and the answer more: (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. Therefore the problem you pose is NP-hard in the sense that if it admits polynomial time algorithm, then P=NP. 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.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |