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.


Published in:
Theoretical Computer Science, 410, 8-10, 977-982
Year:
2009
ISSN:
0304-3975
Keywords:
Laboratories:




 Record created 2010-09-30, last modified 2018-01-28


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)