Record Details

Hardness of approximating independent domination in circle graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Hardness of approximating independent domination in circle graphs
 
Creator DAMIAN-IORDACHE, M
PEMMARAJU, SV
 
Subject connected domination
permutation graphs
set
 
Description 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 is an element of V either u is an element of V' or u has a neighbor in V'. In addition, if no two vertices in V' are adjacent, then V' is called an independent dominating set; if G[V'] is connected, then V' is called a connected dominating set. Keil (Discrete Applied Mathematics, 42 (1993), 51-63) shows that the minimum dominating set problem and the minimum connected dominating set problem are both NP-complete even for circle graphs. He leaves open the complexity of the minimum independent dominating set problem. In this paper we show that the minimum independent dominating set problem on circle graphs is NP-complete. Furthermore we show that for any epsilon, 0 < < 1, there does not exist an n()-approximation algorithm for the minimum independent dominating set problem on n-vertex circle graphs, unless P = NP. Several other related domination problems on circle graphs are also shown to he as hard to approximate.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T13:00:21Z
2011-12-15T09:11:10Z
2011-10-23T13:00:21Z
2011-12-15T09:11:10Z
2000
 
Type Article; Proceedings Paper
 
Identifier ALGORITHMS AND COMPUTATIONS,1741,56-69
3-540-66916-7
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15136
http://hdl.handle.net/100/1891
 
Source 10th Annual International Symposium on Algorithms and Computation (ISAAC 99),CHENNAI, INDIA,DEC 16-18, 1999
 
Language English