2026-07-22T21:03:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9619 2024-03-06T10:44:33Z ddc:004 open_access

Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames Bandyapadhyay, Sayan Maheshwari, Anil Mehrabi, Saeed Suri, Subhash Minimum dominating set Rectangles and L-frames Approximation schemes Local search APX-hardness 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay and Anil Maheshwari and Saeed Mehrabi and Subhash Suri 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.37 urn:nbn:de:0030-drops-96198 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.37 eng https://creativecommons.org/licenses/by/3.0/legalcode