Bandyapadhyay, Sayan ;
Maheshwari, Anil ;
Mehrabi, Saeed ;
Suri, Subhash
Approximating Dominating Set on Intersection Graphs of Rectangles and Lframes
Abstract
We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widelyused geometric objects such as rectangles, no sublogarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NPhard 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 "diagonalanchored" rectangles, providing the first O(1)approximation for the problem on a nontrivial subclass of rectangles. It is not hard to see that the MDS problem on "diagonalanchored" rectangles is the same as the MDS problem on "diagonalanchored" Lframes: 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 "diagonalanchored" Lframes. On the other hand, we show that the problem is APXhard in case the input Lframes intersect the diagonal, or the horizontal segments of the Lframes intersect a vertical line. However, as we show, the problem is lineartime solvable in case the Lframes intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the socalled "edge intersection model" and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).
BibTeX  Entry
@InProceedings{bandyapadhyay_et_al:LIPIcs:2018:9619,
author = {Sayan Bandyapadhyay and Anil Maheshwari and Saeed Mehrabi and Subhash Suri},
title = {{Approximating Dominating Set on Intersection Graphs of Rectangles and Lframes}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {37:137:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9619},
URN = {urn:nbn:de:0030drops96198},
doi = {10.4230/LIPIcs.MFCS.2018.37},
annote = {Keywords: Minimum dominating set, Rectangles and Lframes, Approximation schemes, Local search, APXhardness}
}
2018
Keywords: 

Minimum dominating set, Rectangles and Lframes, Approximation schemes, Local search, APXhardness 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

2018 