# Is the minimum weight independent dominating set np-complete in chordal graphs?

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?

1. The weighted independent domination problem is NP-complete for chordal graphs by G. J. Chang (2004)
2. Fundamentals of Domination in Graphs by T. W. Haynes, S. Hedetniemi and P. Slater (1998)
• I edited your question to cite the article more robustly. Your additional question about planar graphs (overwritten edit) should be in a new question, not this one. – Raphael Mar 25 '14 at 0:48
• As for this question, can you explain more detail how the authors of [1] "seem to contradict" themselves? – Raphael Mar 25 '14 at 0:49
• Added a few details with a quote of the important piece that I was referring to. – user4734 Mar 25 '14 at 0:52

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.