Domination on Geometric Intersection Graphs

On intersection graphs of unit disks, we can give an improved approximation scheme for Minimum (Connected) Dominating Set, which is an EPTAS if the density of the disks is 'bounded' and a PTAS in general. The scheme is essentially optimal: Under strong complexity assumptions, its running time cannot be improved upon (up to constants) and if the disk density is not 'bounded', then no EPTAS exists. The ideas behind this scheme do not seem to carry over to intersection graphs of arbitrary sized objects. Instead, we present a general theorem to approximate Minimum (Connected) Dominating Set, which yields a polynomial-time constant-factor approximation algorithm on a large number of object types, for instance on intersection graphs of homothetic convex polygons and of bounded aspect-ratio rectangles. By a different method, if the objects are 'disk-like' and every point of the plane is overlapped by a bounded number of objects, we also obtain a constant-factor approximation algorithm. Intriguingly, if every point is overlapped by an arbitrary number of disk-like objects, then the problem is as hard as on general graphs.