Domination in geometric intersection graphs. (English) Zbl 1136.68568
Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 747-758 (2008).
Summary: 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 + \epsilon )\)-approximation algorithm.
For the entire collection see [Zbl 1133.68008].
For the entire collection see [Zbl 1133.68008].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W25 | Approximation algorithms |
References:
| [1] | Alimonti, P.; Kann, V., Some APX-completeness results for cubic graphs, Theoret. Comput. Sci., 237, 1-2, 123-134 (2000) · Zbl 0939.68052 · doi:10.1016/S0304-3975(98)00158-3 |
| [2] | Ambühl, C.; Erlebach, T.; Mihalák, M.; Nunkesser, M.; Díaz, J.; Jansen, K.; Rolim, J. D.; Zwick, U., Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs, Proc. APPROX-RANDOM 2006, 3-14 (2006), Heidelberg: Springer, Heidelberg · Zbl 1148.05308 |
| [3] | Baker, B. S., Approximation Algorithms for NP-Complete Problems on Planar Graphs, J. ACM, 41, 1, 153-180 (1994) · Zbl 0807.68067 |
| [4] | Bar-Yehuda, R.; Even, S., A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem, J. Algorithms, 2, 2, 198-203 (1981) · Zbl 0459.68033 · doi:10.1016/0196-6774(81)90020-1 |
| [5] | Brönnimann, H.; Goodrich, M. T., Almost Optimal Set Covers in Finite VC-Dimension, Discrete Comput. Geometry, 14, 4, 463-479 (1995) · Zbl 0841.68122 · doi:10.1007/BF02570718 |
| [6] | Chan, T. M., Polynomial-time Approximation Schemes for Packing and Piercing Fat Objects, J. Algorithms, 46, 2, 178-189 (2003) · Zbl 1030.68093 · doi:10.1016/S0196-6774(02)00294-8 |
| [7] | Chang, M.-S., Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs, SIAM J. Comput., 27, 6, 1671-1694 (1998) · Zbl 0911.05051 · doi:10.1137/S0097539792238431 |
| [8] | Chlebík, M.; Chlebíková, J.; Albers, S.; Radzik, T., Approximation Hardness of Dominating Set Problems, Algorithms - ESA 2004, 192-203 (2004), Heidelberg: Springer, Heidelberg · Zbl 1111.68782 |
| [9] | 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) · Zbl 1165.68034 · doi:10.1137/050629276 |
| [10] | Clark, B. N.; Colbourn, C. J.; Johnson, D. S., Unit Disk Graphs, Discrete Math., 86, 1-3, 165-177 (1990) · Zbl 0739.05079 · doi:10.1016/0012-365X(90)90358-O |
| [11] | Clarkson, K. L.; Varadarajan, K. R., Improved Approximation Algorithms for Geometric Set Cover, Discrete Comput. Geometry, 37, 1, 43-58 (2007) · Zbl 1106.68121 · doi:10.1007/s00454-006-1273-8 |
| [12] | Efrat, A.; Sharir, M., The Complexity of the Union of Fat Objects in the Plane, Discrete Comput. Geometry, 23, 2, 171-189 (2000) · Zbl 0944.68183 · doi:10.1007/PL00009494 |
| [13] | Erlebach, T.; Jansen, K.; Seidel, E., Polynomial-time Approximation Schemes for Geometric Intersection Graphs, SIAM J. Comput., 34, 6, 1302-1323 (2005) · Zbl 1081.68031 · doi:10.1137/S0097539702402676 |
| [14] | Even, G.; Rawitz, D.; Sharar, S., Hitting Sets when the VC-Dimension is Small, Inform. Process. Lett., 95, 2, 358-362 (2005) · Zbl 1184.68632 · doi:10.1016/j.ipl.2005.03.010 |
| [15] | Feige, U., A Threshold of ln n for Approximating Set Cover, J. ACM, 45, 4, 634-652 (1998) · Zbl 1065.68573 |
| [16] | Hochbaum, D. S., Approximation Algorithms for the Set Covering and Vertex Cover Problems, SIAM J. Comput., 11, 3, 555-556 (1982) · Zbl 0486.68067 · doi:10.1137/0211045 |
| [17] | Hochbaum, D. S.; Maass, W., Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI, J. ACM, 32, 1, 130-136 (1985) · Zbl 0633.68027 |
| [18] | 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) · Zbl 0894.68105 · doi:10.1006/jagm.1997.0903 |
| [19] | 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) · Zbl 0594.52004 · doi:10.1007/BF02187683 |
| [20] | 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) · Zbl 1054.05040 |
| [21] | Koebe, P., Kontaktprobleme der konformen Abbildung, Ber. Ver. Sächs. Ak. Wiss. Leipzig, Math.-Phys. Kl., 88, 141-164 (1936) · Zbl 0017.21701 |
| [22] | 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) · Zbl 0821.90128 · doi:10.1002/net.3230250205 |
| [23] | Marx, D.; Bodlaender, H. L.; Langston, M. A., Parameterized Complexity of Independence and Domination on Geometric Graphs, Parameterized and Exact Computation, 154-165 (2006), Heidelberg: Springer, Heidelberg · Zbl 1154.68431 · doi:10.1007/11847250_14 |
| [24] | 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) · Zbl 0883.68100 |
| [25] | Nieberg, T.; Hurink, J. L.; Erlebach, T.; Persinao, G., A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs, Approximation and Online Algorithms, 296-306 (2006), Heidelberg: Springer, Heidelberg · Zbl 1177.68258 · doi:10.1007/11671411_23 |
| [26] | van Leeuwen, E. J.; Arge, L.; Freivalds, [.w.c. L., Better Approximation Schemes for Disk Graphs, Algorithm Theory - SWAT 2006, 316-327 (2006), Heidelberg: Springer, Heidelberg · Zbl 1142.68617 · doi:10.1007/11785293_30 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
