1
$\begingroup$

Clark et al. proved that the clique problem is polynomial-time solvable in unit disk graphs. Does anyone know if this result holds still if the disks are allowed to be different sizes? Or do such "non-unit disk graphs" in fact constitute all graphs, and thus the clique problem is NP-hard again? (I've been able to draw some of the impossible unit disk graphs found here with different sized disks.)

EDIT: as stated in the comments, disk graphs are a strict subset of graphs. In this paper the authors give an example: $K_{3,3}$ is not a disk graph.

$\endgroup$
2
  • $\begingroup$ Interesting question, I don't know. But disk graphs do not constitute all graphs. $\endgroup$
    – Juho
    Oct 15 '21 at 16:05
  • 1
    $\begingroup$ As a general tip, a good place to start searching with these questions is to take a look at the ISGCI: the page on the class of disk graphs has clique as 'unknown'. $\endgroup$
    – Discrete lizard
    Oct 15 '21 at 17:09
2
$\begingroup$

This is an open problem

In a paper from 2020, Maximum Clique in Disk-Like Intersection Graphs by Édouard Bonnet, Nicolas Grelier, and Tillmann Miltzow, the authors note in the abstract that

(...) The main open question (...) is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard.

and proceed to present their results, which can be seen as progress towards proving the problem one way or another.

$\endgroup$

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.