The Minimum-Cost Dominating Set Problem is specified by an undirected graph G =

Question

The Minimum-Cost Dominating Set Problem is specified by an undirected graph G = (V, E) and costs c(v) on the nodes v V. A subset S V is said to be a dominating set if all nodes u VS have an edge (u, v) to a node v in S. (Note the difference between dominating sets and vertex covers: in a dominating set, it is fine to have an edge (u, v) with neither u nor v in the set S as long as both u and v have neighbors in S.)

(a) Give a polynomial-time algorithm for the Dominating Set Problem for the special case in which G is a tree.

(b) Give a polynomial-time algorithm for the Dominating Set Problem for the special case in which G has tree-width 2, and we are also given a tree decomposition of G with width 2.

Explanation / Answer

a.

boolean Vertex-Covers(G, k) {
if (G contains kn edges) return false
if (G contains no edges) return true

let (u, v) be any edge of G
a = Vertex-Covers(G - {u}, k-1)
b = Vertex-Covers(G - {v}, k-1)
return a or b

b.
Note the difference between Dominate Set and Vertex Cover Set.
Hence, for a no-leaf node u, if u is in, its children can be either in or out. If u is out, then any of the two following cases must
be true:
a. u's parent node is in.
b. at least one of u's children nodes is in.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.