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

Abstract

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 P 6D NP, 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).