Domination in Geometric Intersection Graphs
For intersection graphs of disks and other fat objects, polynomial-time approximation schemes are known for the independent set and vertex cover problems, but the existing techniques were not able to deal with the dominating set problem except in the spec
- PDF / 530,112 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 46 Downloads / 221 Views
2
Department of Computer Science, University of Leicester, University Road, Leicester LE1 7RH, UK [email protected] CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands [email protected]
Abstract. For intersection graphs of disks and other fat objects, polynomial-time approximation schemes are known for the independent set and vertex cover problems, 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 approximability of the dominating set problem in geometric intersection graphs. On the one hand, we show that for intersection graphs of arbitrary fat objects, the dominating set problem is as hard to approximate as for general graphs. For intersection 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 algorithms 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.
1 Introduction We study the approximability of the minimum dominating set problem in geometric intersection graphs. Given an undirected graph G = (V, E), a set D ⊆ V is a dominating set if every v ∈ V is in D or has a neighbor in D. The aim of Minimum Dominating Set (MDS) is to compute for a given graph a dominating set of minimum cardinality. Although for general graphs the approximability of MDS has been settled [15,8], the problem is open for numerous graph classes, such as geometric intersection graphs. Geometric intersection graphs are graphs in which the vertices represent geometric objects and two vertices are adjacent if the corresponding objects intersect. Studying approximation algorithms for fundamental graph optimization problems on such graphs has led to several new techniques, in particular the geometric shifting technique [17], which can be used to obtain polynomial-time approximation schemes (PTASs) for a number of problems, such as Maximum Independent Set and Minimum Vertex Cover in unit disk graphs [18] and in general disk graphs [13,6,26]. These algorithms extend to any constant number of dimensions and arbitrary fat objects (including e.g. squares or other regular polygons in the two-dimensional case). Interestingly, as pointed out in [13], these techniques do not seem sufficient for handling MDS in intersection graphs of objects of different sizes. To the best of our
Partially supported by the Dutch BSIK/BRICKS project.
E.S. Laber et al. (Eds.): LATIN 2008, LNCS 4957, pp. 747–758, 2008. c Springer-Verlag Berlin Heidelberg 2008
748
T. Erlebach and E.J. van Leeuwen
knowledge, there are no results for intersection graphs of disks, squares, etc. beyond the (1 + ln n)-approximation ratio that can be achie
Data Loading...
