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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1-2), 123–134 (2000)
Ambühl, C., Erlebach, T., Mihalák, M., Nunkesser, M.: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. In: Díaz, J., Jansen, K., Rolim, J.D., Zwick, U. (eds.) Proc. APPROX-RANDOM 2006. LNCS, vol. 4110, pp. 3–14. Springer-Verlag, Berlin/Heidelberg (2006)
Baker, B.S.: Approximation Algorithms for NP-Complete Problems on Planar Graphs. J. ACM 41(1), 153–180 (1994)
Bar-Yehuda, R., Even, S.: A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem. J. Algorithms 2(2), 198–203 (1981)
Brönnimann, H., Goodrich, M.T.: Almost Optimal Set Covers in Finite VC-Dimension. Discrete Comput. Geometry 14(4), 463–479 (1995)
Chan, T.M.: Polynomial-time Approximation Schemes for Packing and Piercing Fat Objects. J. Algorithms 46(2), 178–189 (2003)
Chang, M.-S.: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs. SIAM J. Comput. 27(6), 1671–1694 (1998)
Chlebík, M., Chlebíková, J.: Approximation Hardness of Dominating Set Problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 192–203. Springer-Verlag, Berlin/Heidelberg (2004)
Chlebík, M., Chlebíková, J.: The Complexity of Combinatorial Optimization Problems on d-Dimensional Boxes. SIAM J. Discrete Math. 21(1), 158–169 (2007)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit Disk Graphs. Discrete Math. 86(1–3), 165–177 (1990)
Clarkson, K.L., Varadarajan, K.R.: Improved Approximation Algorithms for Geometric Set Cover. Discrete Comput. Geometry 37(1), 43–58 (2007)
Efrat, A., Sharir, M.: The Complexity of the Union of Fat Objects in the Plane. Discrete Comput. Geometry 23(2), 171–189 (2000)
Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time Approximation Schemes for Geometric Intersection Graphs. SIAM J. Comput. 34(6), 1302–1323 (2005)
Even, G., Rawitz, D., Sharar, S.: Hitting Sets when the VC-Dimension is Small. Inform. Process. Lett. 95(2), 358–362 (2005)
Feige, U.: A Threshold of ln n for Approximating Set Cover. J. ACM 45(4), 634–652 (1998)
Hochbaum, D.S.: Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM J. Comput. 11(3), 555–556 (1982)
Hochbaum, D.S., Maass, W.: Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. J. ACM 32(1), 130–136 (1985)
Hunt III, D.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. J. Algorithms 26(2), 238–274 (1998)
Kedem, K., Livne, R., Pach, J., Sharir, M.: On the Union of Jordan Regions and Collision-Free Translational Motion Amidst Polygonal Obstacles. Discrete Comput. Geometry 1, 59–70 (1986)
Kim, S.-J., Kostochka, A., Nakprasit, K.: On the Chromatic Number of Intersection Graphs of Convex Sets in the Plane. Electr. J. Combinatorics 11, #R52 (2004)
Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Ver. Sächs. Ak. Wiss. Leipzig, Math.-Phys. Kl. 88, 141–164 (1936)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59–68 (1995)
Marx, D.: Parameterized Complexity of Independence and Domination on Geometric Graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 154–165. Springer-Verlag, Berlin/Heidelberg (2006)
Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Separators for Sphere-Packings and Nearest Neighbor Graphs. J. ACM 44(1), 1–29 (1997)
Nieberg, T., Hurink, J.L.: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 296–306. Springer-Verlag, Berlin/Heidelberg (2006)
van Leeuwen, E.J.: Better Approximation Schemes for Disk Graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 316–327. Springer-Verlag, Berlin/Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Erlebach, T., van Leeuwen, E.J. (2008). Domination in Geometric Intersection Graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_64
Download citation
DOI: https://doi.org/10.1007/978-3-540-78773-0_64
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78772-3
Online ISBN: 978-3-540-78773-0
eBook Packages: Computer ScienceComputer Science (R0)