Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

Authors Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, Subhash Suri



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.37.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Sayan Bandyapadhyay
  • Department of Computer Science, University of Iowa, Iowa City, USA
Anil Maheshwari
  • School of Computer Science, Carleton University, Ottawa, Canada
Saeed Mehrabi
  • School of Computer Science, Carleton University, Ottawa, Canada
Subhash Suri
  • Department of Computer Science, UC Santa Barbara, California, USA

Cite AsGet BibTex

Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, and Subhash Suri. Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.37

Abstract

We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP-hard even when all the rectangles are "anchored" at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any epsilon>0, there exists a (2+epsilon)-approximation algorithm for the MDS problem on "diagonal-anchored" rectangles, providing the first O(1)-approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on "diagonal-anchored" rectangles is the same as the MDS problem on "diagonal-anchored" L-frames: the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a (2+epsilon)-approximation for the problem with "diagonal-anchored" L-frames. On the other hand, we show that the problem is APX-hard in case the input L-frames intersect the diagonal, or the horizontal segments of the L-frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L-frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called "edge intersection model" and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
  • Theory of computation → Computational geometry
Keywords
  • Minimum dominating set
  • Rectangles and L-frames
  • Approximation schemes
  • Local search
  • APX-hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Andrei Asinowski, Elad Cohen, Martin Charles Golumbic, Vincent Limouzy, Marina Lipshteyn, and Michal Stern. Vertex intersection graphs of paths on a grid. J. Graph Algorithms Appl., 16(2):129-150, 2012. Google Scholar
  2. Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of Euclidean k-means. In SoCG 2015, Netherlands, 754-767, volume 34 of Leibniz International Proceedings in Informatics (LIPIcs), 2015. Google Scholar
  3. Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, and Subhash Suri. Approximating dominating set on intersection graphs of L-frames. CoRR, abs/1803.06216, 2018. Google Scholar
  4. Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz. Optimization problems in multiple-interval graphs. ACM Trans. Algorithms, 6(2):40:1-40:18, 2010. Google Scholar
  5. Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halldórsson, Magnús M. Halldórsson, Thomas Hixon, and Juraj Stacho. Max point-tolerance graphs. Discrete Applied Mathematics, 216:84-97, 2017. Google Scholar
  6. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. Google Scholar
  7. H. S. Chao, Fang-Rong Hsu, and Richard C. T. Lee. An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discrete Applied Mathematics, 102(3):159-173, 2000. Google Scholar
  8. Victor Chepoi and Stefan Felsner. Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom., 46(9):1036-1041, 2013. Google Scholar
  9. José R. Correa, Laurent Feuilloley, Pablo Pérez-Lantero, and José A. Soto. Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity. DCG, 53(2):344-365, 2015. Google Scholar
  10. Mirela Damian and Sriram V. Pemmaraju. APX-hardness of domination problems in circle graphs. Inf. Process. Lett., 97(6):231-237, 2006. Google Scholar
  11. Mirela Damian-Iordache and Sriram V. Pemmaraju. A (2+epsilon)-approximation scheme for minimum domination on circle graphs. J. Algorithms, 42(2):255-276, 2002. Google Scholar
  12. Minati De and Abhiruk Lahiri. Geometric dominating set and set cover via local search. CoRR, abs/1605.02499, 2016. URL: http://arxiv.org/abs/1605.02499.
  13. Mark de Berg and Amirali Khosravi. Optimal binary space partitions for segments in the plane. Int. J. Comput. Geometry Appl., 22(3):187-206, 2012. Google Scholar
  14. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1):439-485, 2005. Google Scholar
  15. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633, 2014. Google Scholar
  16. Thomas Erlebach and Erik Jan van Leeuwen. Domination in geometric intersection graphs. In LATIN 2008, Búzios, Brazil, April 7-11, 2008, Proceedings, pages 747-758, 2008. Google Scholar
  17. Matt Gibson and Imran A. Pirwani. Algorithms for dominating set in disk graphs: Breaking the logn barrier - (extended abstract). In ESA 2010, UK, pages 243-254, 2010. Google Scholar
  18. Martin Charles Golumbic, Marina Lipshteyn, and Michal Stern. Edge intersection graphs of single bend paths on a grid. Networks, 54(3):130-138, 2009. Google Scholar
  19. Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy. Packing and covering with non-piercing regions. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 47:1-47:17, 2016. Google Scholar
  20. Daniel Heldt, Kolja B. Knauer, and Torsten Ueckerdt. Edge-intersection graphs of grid paths: The bend-number. Discrete Applied Mathematics, 167:144-162, 2014. Google Scholar
  21. Joseph D. Horton and Kyriakos Kilakos. Minimum edge dominating sets. SIAM J. Discrete Math., 6(3):375-387, 1993. Google Scholar
  22. J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, and Martin Vatshelle. An algorithm for the maximum weight independent set problem on outerstring graphs. Comput. Geom., 60:19-25, 2017. Google Scholar
  23. Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, pages 154-165, 2006. Google Scholar
  24. Saeed Mehrabi. Approximating domination on intersection graphs of paths on a grid. In 15th International Workshop on Approximation and Online Algorithms (WAOA 2017), Vienna, Austria, pages 76-89, 2017. Google Scholar
  25. Apurva Mudgal and Supantha Pandit. Covering, hitting, piercing and packing rectangles intersecting an inclined line. In COCOA 2015, Houston, TX, USA, pages 126-137, 2015. Google Scholar
  26. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  27. Supantha Pandit. Dominating set of rectangles intersecting a straight line. In CCCG 2017, Ottawa, Ontario, Canada, pages 144-149, 2017. Google Scholar
  28. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 475-484, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail