0
$\begingroup$

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?

Improve this question
$\endgroup$
1
  • $\begingroup$ You might want a list of NP-hard cases? I think the hardness depends on the dimension, the shape and geometric restriction, and in some case it's not NP-hard. $\endgroup$
    – Hao Chen
    Commented Nov 13, 2014 at 11:04

1 Answer 1

Reset to default
5
$\begingroup$

According to graphclasses.org it is NP-Hard in

grid intersection: http://graphclasses.org/classes/gc_739.html

rectangle intersection: http://graphclasses.org/classes/gc_1179.html

Click in "Details" for reference or other graph class.

The query for intersection is:

http://graphclasses.org/classes.cgi?search=intersection

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .