The complexity of dominating set in geometric intersection graphs. (English) Zbl 1421.68071
Summary: We study the parameterized complexity of the dominating set problem in geometric intersection graphs.
- ●
- In one dimension, we investigate intersection graphs induced by translates of a fixed pattern \(Q\) that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever \(Q\) contains at least one interval, and whenever \(Q\) contains no intervals and for any two point pairs in \(Q\) the distance ratio is rational. The remaining case where \(Q\) contains no intervals but does contain an irrational distance ratio is shown to be \(\mathsf{NP}\)-complete and contained in \(\mathsf{FPT}\) (when parameterized by the solution size).
- ●
- In two and higher dimensions, we prove that Dominating Set is contained in \(\mathsf{W} [1]\) for intersection graphs of semi-algebraic sets with constant description complexity. So far this was only known for unit squares. Finally, we establish \(\mathsf{W} [1]\)-hardness for a large class of intersection graphs.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Arnon, Dennis S.; Collins, George E.; McCallum, Scott, Cylindrical algebraic decomposition I: the basic algorithm, SIAM J. Comput., 13, 4, 865-877 (1984) · Zbl 0562.14001 |
| [2] | Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10 (2006), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 1102.14041 |
| [3] | de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark, Computational Geometry: Algorithms and Applications (2008), Springer-Verlag · Zbl 1140.68069 |
| [4] | Chang, Maw-Shang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput., 27, 6, 1671-1694 (1998) · Zbl 0911.05051 |
| [5] | Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket, Parameterized Algorithms (2015), Springer · Zbl 1334.90001 |
| [6] | Downey, Rodney G.; Fellows, Michael R., Fixed-parameter tractability and completeness I: basic results, SIAM J. Comput., 24, 4, 873-921 (1995) · Zbl 0830.68063 |
| [7] | Erlebach, Thomas; Jan van Leeuwen, Erik, Domination in geometric intersection graphs, (Sany Laber, Eduardo; Bornstein, Claudson F.; Nogueira, Loana Tito; Faria, Luérbio, LATIN 2008, Proceedings. LATIN 2008, Proceedings, LNCS, vol. 4957 (2008), Springer), 747-758 · Zbl 1136.68568 |
| [8] | Fellows, Michael R.; Hermelin, Danny; Rosamond, Frances A.; Vialette, Stéphane, On the parameterized complexity of multiple-interval graph problems, Theoret. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038 |
| [9] | Flum, Jörg; Grohe, Martin, Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series (2006), Springer · Zbl 1143.68016 |
| [10] | Har-Peled, Sariel, Being fat and friendly is not enough (2009), arXiv preprint |
| [11] | Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J., Domination in Graphs: Advanced Topics, Pure Appl. Math. (1998), Marcel Dekker, Inc. · Zbl 0883.00011 |
| [12] | Kant, Goos, Hexagonal grid drawings, (Mayr, Ernst W., WG ’92, Proceedings. WG ’92, Proceedings, LNCS, vol. 657 (1992), Springer), 263-276 · Zbl 0925.05056 |
| [13] | Marx, Dániel, Parameterized complexity of independence and domination on geometric graphs, (Bodlaender, Hans L.; Langston, Michael A., IWPEC 2006, Proceedings. IWPEC 2006, Proceedings, LNCS, vol. 4169 (2006), Springer), 154-165 · Zbl 1154.68431 |
| [14] | Marx, Dániel; Pilipczuk, Michał, Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams (2015), arXiv preprint · Zbl 1422.68253 |
| [15] | Raman, Venkatesh; Saurabh, Saket, Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles, Algorithmica, 52, 2, 203-225 (2008) · Zbl 1170.68019 |
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.
