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

摘要

We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P{sub}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 2P{sub}3-free graphs in polynomial time within a factor of n{sup}(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 2P{sub}3-free graph is restricted to being weakly chordal (and thereby perfect).