Constant-factor approximation algorithms for domination problems on circle graphs (Q4511218)

A circle graph is a graph whose vertex set is a set of chords of a circle and in which two vertices are adjacent if and only if they intersect each other. A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is dominating in \(G\), if each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). If moreover the subgraph of \(G\) induced by \(D\) is connected, then \(D\) is a connected dominating set of \(G\). If that subgraph has no isolated vertex, then \(D\) is a total dominating set of \(G\). In the paper these concepts are treated from the viewpoint of computational complexity. The minimum dominating set problems (MDS), the minimum connected domination set problem (MCDS) and the minimum total dominating set problem (MTDS) are considered for circle graphs. All of them are NP-complete even for circle graphs. Approximating algorithms for all those problems are presented, each running in time \(O(n^2+ nm)\), where \(n\) is the number of vertices and \(m\) is the number of edges of \(G\). For the entire collection see [Zbl 0933.00045].