polynomial-time algorithm for finding dominating set in a tree

Question

Let G = (V,E) be an undirected graph. A subset S ⊆ V of nodes in G is called a "dominating set" if for all v ∈ V, we have v ∈ S or there is some node u ∈ S such that (u,v) ∈ E. In other words every node in V \ S is connected by an edge to some node in S. Given non-negative weights w(v) on the nodes of V the goal is to find a minimum-weight dominating set in G. (Note: This problem is known to be NP-Hard in general graphs) We need to design a POLYNOMIAL time algorithm fir this problem when G is a tree.

I read about Steiner tree problem on Wiki, which is somewhat related to this, but still confused.

How do we need to go about this?

Answer 1

I found this paper, which gives a dynamic programming algorithm for the vertex-edge weighted domination number of a tree on page 19. For the "tree ordering", you can use a post-order traversal ordering. You will have to modify it a bit (e.g., let all edge weights be zero), and you should find a way to construct the solution from the DP matrix. Hope this helps.

http://www.math.ntu.edu.tw/~mathlib/preprint/2011-01.pdf