Approximating Minimum Dominating Set on String Graphs
share
In this paper, we give approximation algorithms for the Minimum Dominating Set (MDS) problem on string graphs and its subclasses. A path is a simple curve made up of alternating horizontal and vertical line segments. A k-bend path is a path made up of at most k + 1 line segments. An L-path is a 1-bend path having the shape `L'. A vertically-stabbed-L graph is an intersection graph of L-paths intersecting a common vertical line. We give 8-approximation algorithm for MDS problem on vertically-stabbed-L graphs whose APX-hardness was shown by Bandyapadhyay et al. (MFCS, 2018). To prove the above result, we needed to study the Stabbing segments with rays (SSR) problem introduced by Katz et al. (Comput. Geom. 2005). In the SSR problem, the input is a set of (disjoint) leftward-directed rays, and a set of (disjoint) vertical segments. The objective is to select a minimum number of rays that intersect all vertical segments. We give a O((n+m) (n+m))-time 2-approximation algorithm for the SSR problem where n and m are the number of rays and segments in the input. A unit k-bend path is a k-bend path whose segments are of unit length. A graph is a unit B_k-VPG graph if it is an intersection graph of unit k-bend paths. Any string graph is a unit-B_k-VPG graph for some finite k. Using our result on SSR-problem, we give a polynomial time O(k^4)-approximation algorithm for MDS problem on unit B_k-VPG graphs for k≥ 0.
READ FULL TEXT