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

We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P(3)-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as all induced subgraph. We show that, if P not equal NP, the problem cannot be approximated for 2P(3)-freegraphs in polynomial time within a factor of n(1-epsilon) for any constant epsilon > 0, where n is the number of vertices ill the graph. Moreover, we show that the result holds even if the 2P(3)-free graph is restricted to being weakly chordal (and thereby perfect). (C) 2008 Elsevier B.V. All rights reserved.