The weighted independent domination problem is NP-complete for chordal graphs
An independent dominating set of a graph G=(V,E) is a pairwise non-adjacent subset D of V such that every vertex not in D is adjacent to at least one vertex in D. Suppose each vertex in V is associated with a weight which is a real number. The weighted independent domination problem is to find an independent domination set of minimum total weights. This paper records an unpublished result of 20 years ago that the weighted independent domination problem is NP-complete for chordal graphs.
weight independent domination np-complete chordal graph