Every generalized octhedron O_{t} is a unit-disk graph. Nevertheless it turns out that a maximum clique can be found in polynomial time provided we have the model available. This is a nice example where reconstruction could be motivated by some optimization problem. Unfortunately, unit-disk graphs cannot be reconstructed efficiently---the recognition problem for unit-disk graphs is NP-hard [BK98]. Thus the complexity status of the maximum clique problem restricted to unit-disk graphs (without a representation given) is still open.
[CCJ90]: There is some O(n^{4.5})-time algorithm to find a maximum clique in a unit-disk graph provided the model is given. |
Proof: First we provide a fresh view on the model. Let G=(V,E) be the intersection graph of the family (S_{x}/x V) of unit-disks in the plane. Let p_{x} be the center of S_{x}. Obviously S_{x} and S_{y} intersect iff the distance between p_{x} and p_{y} is at most 2. Therefore it suffices to look at these points p_{x}. For xy E, let A_{xy} denote the set of all z V for which p_{z} is contained in both (closed) circles around p_{x} and p_{y} with radius d(p_{x}p_{y}). Certainly each such z (different from x,y) must be adjacent to both x and y in G. These sets A_{xy} are not complete, but they induce complements of bipartite graphs. This can be seen by drawing the line between p_{x} and p_{y}. Each half has diameter less than 2, therefore vertices corresponding to points in each half are pairwise adjacent. Maximum cliques in complements of bipartite graphs, i.e. maximum independent sets in bipartite graphs, can be found in time O(n^{2.5}) via maximum matching in bipartite graphs. Any clique C of G is contained in A_{xy} where we choose x,y V(C) with maximum distance. Thus by finding maximum cliques in each of the n^{2} graphs A_{xy}, we find a maximum clique of G. |
What about the MAXCLIQUE problem for unit-disk graphs without a representation given? Can a maximum clique at least be approximated then? |
Back to the start page for intersection graphs?