Homework 8

CS 482 - Summer 2007

Due: Friday, Aug 10 [changed to Monday, Aug 13]

Problem C has been corrected: It was listed as problem 9, but problem 10 is the correct one.

  1. [Dominating Sets; 10 points] A dominating set on a graph G is a subset S of nodes such that every node v of G is either in S or is adjacent to at least one node in S.  In the Dominating Set Problem (DSP), you are given a graph G = (V,E) and an integer k, and the goal is to determine if G has a dominating set of size k.
     
    1. Give an example of a graph whose smallest dominating set is different from its smallest vertex cover. 
       
    2. Show that DSP is NP-complete. [Hint: Try a reduction from 3-SAT, using 3 nodes per variable and one node per clause.]
       
    3. Part (2) implies that we don't know of a polynomial-time algorithm for DSP, but what if the graph is a tree?  Give a polynomial-time algorithm that, given a tree T = (V, E) as input, returns a dominating set of minimum size.
       
    4. Now suppose that every node v has a weight wv. Give a polynomial-time algorithm that, given a tree T = (V,E) and a weight wv for each node v of T, returns the dominating set of minimum total weight.  [Hint: Think Dynamic Programming.]
       
  2. [Loading Trucks (Again); 5 points] Problem 1 in Chapter 11 of the text.
     
  3. [Min Weight Independent Set in a Grid Graph; 5 points] Problem 10 in Chapter 11 of the text.