2017/02/18 by Saeed Mehrabi, Mehrabi, Saeed
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1702.05633
openalex publication_date 2017/02/18 · openalex created_date 2017/03/16 · openalex updated_date 2026/07/28
A graph G is called Bk-VPG (resp., Bk-EPG), for some constant k≥ 0, if it has a string representation on a grid such that each vertex is an orthogonal path with at most k bends and two vertices are adjacent in G if and only if the corresponding strings intersect (resp., the corresponding strings share at least one grid edge). If two adjacent strings of a Bk-VPG graph intersect exactly once, then the graph is called a one-string Bk-VPG graph. In this paper, we study the Maximum Independent Set and Minimum Dominating Set problems on B1-VPG and B1-EPG graphs. We first give a simple O(log n)-approximation algorithm for the Maximum Independent Set problem on B1-VPG graphs, improving the previous O((log n)2)-approximation algorithm of Lahiri et al. (COCOA 2015). Then, we consider the Minimum Dominating Set problem. We give an O(1)-approximation algorithm for this problem on one-string B1-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 B1-EPG graphs, ruling out the possibility of a PTAS unless P=NP. Finally, we give constant-factor approximation algorithms for this problem on two non-trivial subclasses of B1-EPG graphs. To our knowledge, these are the first results for the Minimum Dominating Set problem on B1-EPG graphs, partially answering a question posed by Epstein et al. (WADS 2013).