Book chapter
Hardness of Approximating Independent Domination in Circle Graphs
Algorithms and Computation, pp.56-69
Lecture Notes in Computer Science, Springer Berlin Heidelberg
03/03/2000
DOI: 10.1007/3-540-46632-0_7
Abstract
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 ∈ V either u ∈ 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 ε, 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 be as hard to approximate.
Details
- Title: Subtitle
- Hardness of Approximating Independent Domination in Circle Graphs
- Creators
- Mirela Damian-Iordache - University of IowaSriram V. Pemmaraju - Indian Institute of Technology Indore
- Resource Type
- Book chapter
- Publication Details
- Algorithms and Computation, pp.56-69
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/3-540-46632-0_7
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 03/03/2000
- Academic Unit
- Computer Science
- Record Identifier
- 9984259410602771
Metrics
3 Record Views