Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs.

A graph G = (V,E) is called a circle graph if there is a one-to-one correspondence between vertices in V and a set C of chords in a circle such that two vertices in V are adjacent if and only if the corresponding chords in C intersect. A subset V' of V is a dominating set of G if for all u E V is either u E V' or u has a neighbor in V'. In addition, if G[V'] is connected, then V' is called a connected dominating set; if G[V'] has no isolated vertices, then V' is called a total dominating set. Keil (Discrete Applied Mathematics, 42 (1993), 51-63) shows that the minimum dominating set problem (MDS), the minimum connected dominating set problem (MCDS) and the minimum total domination problem (MTDS) are all NP-complete even for circle graphs. He mentions designing approximation algorithms for these problems as being open. This paper presents O(1)-approximation algorithms for all three problems - MDS, MCDS, and MTDS on circle graphs. For any circle graph with n vertices and m edges, these algorithms take O(n^2+nm) time and O(n^2) space. These results, along with the result on the hardness of approximate minimum independent dominating set on circle graphs (Damian-Iordache and Pemmaraju, in this proceedings) advance our understanding of domination problems on circle graphs significantly.

Main Author: Damian-Iordache, Mirela.
Other Authors: Pemmaraju, Sriram V.
Language: English
Published: 1999
Online Access: