×

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

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.)
PDFBibTeX XMLCite