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)
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Mar 25 '14 at 0:48
  • $\begingroup$ As for this question, can you explain more detail how the authors of [1] "seem to contradict" themselves? $\endgroup$ – Raphael Mar 25 '14 at 0:49
  • $\begingroup$ Added a few details with a quote of the important piece that I was referring to. $\endgroup$ – 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.

  • $\begingroup$ I was under this impression too, but I quote the following piece from [2]: "Somewhat surprisingly, Faber showed that the minimum weight independent dominating set can be solved in polynomial time when restricted to chordal graphs, and thus also restricted to strongly chordal or interval graphs". This was also my understanding, since I was under the impression that this problem had a linear time solution for interval graphs as well. $\endgroup$ – user4734 Mar 25 '14 at 0:59
  • $\begingroup$ The abstract of Faber's paper clearly states that "[w]e present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights." The book could be misleading. $\endgroup$ – Yuval Filmus Mar 25 '14 at 1:21
  • $\begingroup$ I will tread with caution then. I know that the weighted version is polynomial time solvable for interval and circular-arc graphs, but wasn't sure about chordal graphs. $\endgroup$ – user4734 Mar 25 '14 at 1:27
  • $\begingroup$ Check out the NP-hardness proof. It's only about one page long. If you are convinced, then it is NP-hard to solve minimum independent dominating set on weighted chordal graphs. $\endgroup$ – Yuval Filmus Mar 25 '14 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy