The Minimum Dominating Set Problem on Bipartite Circle Graphs: Complexity and Approximation

Abstract

A circle graph is the intersection graph of a set of chords in a circle. A dominating set of a graph $G=(V,E)$ is a subset $D\subseteq V$ such that every vertex in $V\setminus D$ is adjacent to at least one vertex of $D$. Computing a minimum dominating set is known to be NP-hard on circle graphs. In this paper, we study the minimum dominating set problem on bipartite circle graphs, namely, circle graphs admitting a chord representation in which the chords can be partitioned into two color classes such that no two chords of the same color intersect. We prove that the problem remains NP-hard for this restricted graph class by a reduction from Planar Monotone 3-SAT. On the positive side, we present a polynomial-time 2-approximation algorithm and develop a polynomial-time approximation scheme (PTAS) based on local search.

20 pages