Loading...
research article
On the inapproximability of independent domination in 2P3-free perfect graphs
Orlovich, Yury
•
Gordon, Valery
•
de Werra, Dominique
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.
Type
research article
Web of Science ID
WOS:000263945000034
Authors
Orlovich, Yury
•
Gordon, Valery
•
de Werra, Dominique
Publication date
2009
Published in
Volume
410
Issue
8-10
Start page
977
End page
982
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
September 30, 2010
Use this identifier to reference this record