Domination in Geometric Intersection Graphs

Abstract. For intersection graphs of disks and other fat objects, polynomial-time approximation schemes are known for the independent set and vertex cover prob-lems, but the existing techniques were not able to deal with the dominating set problem except in the special case of unit-size objects. We present approximation algorithms and inapproximability results that shed new light on the approxima-bility of the dominating set problem in geometric intersection graphs. On the one hand, we show that for intersection graphs of arbitrary fat objects, the dominat-ing set problem is as hard to approximate as for general graphs. For intersec-tion graphs of arbitrary rectangles, we prove APX-hardness. On the other hand, we present a new general technique for deriving approximation algorithms for various geometric intersection graphs, yielding constant-factor approximation al-gorithms for r-regular polygons, where r is an arbitrary constant, for pairwise homothetic triangles, and for rectangles with bounded aspect ratio. For arbitrary fat objects with bounded ply, we get a (3 + )-approximation algorithm.