A graph G is called B_k-EPG (resp., B_k-VPG), for some constant k ≥ 0, if it has a string representation on an axis-parallel grid such that each vertex is a path with at most k bends and two vertices are adjacent in G if and only if the corresponding strings share at least one grid edge (resp., the corresponding strings intersect each other). If two adjacent strings of a B_k-VPG graph intersect each other exactly once, then the graph is called a one-string B_k-VPG graph. In this paper, we study the MINIMUM DOMINATING SET problem on B_1-EPG and B_1-VPG graphs. We first give an O(1)-approximation algorithm on one-string B_1-VPG graphs, providing the first constant-factor approximation algorithm for this problem. Moreover, we show that the MINIMUM DOMINATING SET problem is APX-hard on B_1-EPG graphs, ruling out the possibility of a PTAS unless P = NP. Finally, to complement our APX-hardness result, we give constant-factor approximation algorithms for the MINIMUM DOMINATING SET problem on two non-trivial subclasses of B_1-EPG graphs.
展开▼
