Dominating Set on Intersection Graphs of Rectangles and L-frames
Saeed Mehrabi
Carleton University

In this talk, we consider the approximability of the minimum dominating set problem on the intersection graphs of axis-parallel rectangles and L-shapes. The problem is known to be NP-hard even if the rectangles are all ``anchored'' at a diagonal line with slope -1 (Pandit, CCCG 2017). For this variant, we give a $(2+\epsilon)$-approximation algorithm for the problem, which is based on a PTAS for a ``one-sided'' variant of the problem. Then, we show the APX-hardness of the problem for two restricted subclasses of these graphs, ruling out the possibility of a PTAS for them. Finally, we consider the problem on the ``edge intersection'' model and show several hardness results for these graphs.

This is a joint work with Sayan Bandyapadhyay, Anil Maheshwari, and Subhash Suri, to appear in MFCS 2018.