I have a found a small article [1] saying (the first paragraph of the introducti

Question

I have a found a small article [1] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to contradict that exact statement.

Moreover, I have found another reference [2] saying that in chordal graphs, it is polynomial time solvable. So which one is it?

Note: I am just trying to reference this result in a project of mine. No need for a proof.

Edit: I am referring to this piece of the introduction: "Domination and most of its variations are NP-complete for chordal graphs (even for the subclass of split graphs) with the exception of independence domination (see [3]). On the other hand, an unpublished proof for the NP-completeness of the weighted independent domination in chordal graphs by the author 20 years ago..." Then in my reference [2], it also states that the weighted version is polynomial time solvable, yet here they say that there is an NP-completeness proof. Am I missing something fundamental?

Explanation / Answer

As the article clearly mentions, unweighted minimum independent dominating set can be solved efficiently (in fact, linear time) for chordal graphs. A glance at the paper shows that this works even if the vertices are given ${0,1}$ weights (rather than all having unit weight). On the other hand, weighted minimum independent dominating set is NP-complete.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.