Orlovich, Y. L., Gordon, V. S., and de Werra, D. (2009)

On the inapproximability of independent domination in 2P3-free perfect graphs , Theoretical Computer Science 410(8-10):977-982.

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.

doi:10.1016/j.tcs.2008.11.023 (click here for the full paper)