A Note on Approximating Weighted Independence on Intersection Graphs of Paths on a Grid

Abstract

A graph $G$ is called $B_k$-VPG, for some constant $k\ge 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 paths intersect each other. The part of a path that is between two consecutive bends is called a segment of the path. In this paper, we study the Maximum-Weighted Independent Set problem on $B_k$-VPG graphs. The problem is known to be NP-complete on $B_1$-VPG graphs, even when the two segments of every path have unit length [12], and $O(\log n)$-approximation algorithms are known on $B_k$-VPG graphs, for $k\le 2$ [3, 14]. In this paper, we give a $(ck+c+1)$-approximation algorithm for the problem on $B_k$-VPG graphs for any $k\ge 0$, where $c>0$ is the length of the longest segment among all segments of paths in the graph. Notice that $c$ is not required to be a constant; for instance, when $c\in O(\log \log n)$, we get an $O(\log \log n)$-approximation or we get an $O(1)$-approximation when $c$ is a constant. To our knowledge, this is the first $o(\log n)$-approximation algorithm for a non-trivial subclass of $B_k$-VPG graphs.

arXiv commentThe related work section is updated. arXiv admin note: text overlap with arXiv:1708.09325

Cited by in corpus (1)

• Approximating Independent Set and Dominating Set on VPG graphs