A (2 + ϵ)-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + &epsiv;)-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n2) time 8-approximation algorithm for this problem and then extend it to an <f>O(n3 + 6/&epsiv;n⌈+ 1⌉m)</f> time (2 + &epsiv;)-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + &epsiv;)-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs. [Copyright &y& Elsevier]