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

We consider the complexity of approximation for the Independent Dominating Set problem in 2P3-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 , the problem cannot be approximated for 2P3-free graphs in polynomial time within a factor of n1−ε for any constant ε>0, where n is the number of vertices in the graph. Moreover, we show that the result holds even if the 2P3-free graph is restricted to being weakly chordal (and thereby perfect).