Orlovich, Yury L.; Gordon, V. S.; de Werra, Dominique Complexity of the approximation of the independent dominating set problem in the class of \(2P_3\)-free perfect graphs. (Russian. English summary) Zbl 1267.05196 Dokl. Nats. Akad. Nauk Belarusi 53, No. 2, 29-33 (2009). Summary: A subset of vertices of a graph is dominating if every vertex outside it has a neighbor in this subset. A subset of vertices is independent if no two vertices in this subset are adjacent. An independent dominating set is a vertex subset that is both independent and dominating. The independent dominating set problem asks for a minimum independent dominating set in a given graph. We show that for any \(\epsilon>0\) the independent dominating set problem for \(2P_3\)-free perfect graphs of order \(n\) cannot be approximated within a factor of \(n^{1-\epsilon}\) in polynomial time, unless \(\mathrm{P}=\mathrm{NP}\). The result holds even if the graph in question is restricted to be weakly chordal. MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:dominating set; independent set; independent dominating set PDFBibTeX XMLCite \textit{Y. L. Orlovich} et al., Dokl. Nats. Akad. Nauk Belarusi 53, No. 2, 29--33 (2009; Zbl 1267.05196)