On the inapproximability of independent domination in 2 P 3 -free perfect graphs

We consider the complexity of approximation for the Independent Dominating Set problem in 2 P 3 -free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as an induced subgraph. We show that, if P ≠ NP , the problem cannot be approximated for 2 P 3 -f...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-03, Vol.410 (8), p.977-982
Main Authors: Orlovich, Yury L., Gordon, Valery S., de Werra, Dominique
Format: Article
Language:English
Subjects:
[formula omitted]-free graph
Approximability
Independent dominating set
Perfect graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the complexity of approximation for the Independent Dominating Set problem in 2 P 3 -free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as an induced subgraph. We show that, if P ≠ NP , the problem cannot be approximated for 2 P 3 -free graphs in polynomial time within a factor of n 1 − ε for any constant ε > 0 , where n is the number of vertices in the graph. Moreover, we show that the result holds even if the 2 P 3 -free graph is restricted to being weakly chordal (and thereby perfect).
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2008.11.023