2
$\begingroup$

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Mar 25, 2014 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
    Commented Mar 25, 2014 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
    Commented Mar 25, 2014 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
    Commented Mar 25, 2014 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.