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.
- [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.
- Give an example of a graph whose smallest dominating set is different
from its smallest vertex cover.
- Show that DSP is NP-complete. [Hint: Try a reduction from 3-SAT, using
3 nodes per variable and one node per clause.]
- 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.
- 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.]
- [Loading Trucks (Again); 5 points] Problem 1 in Chapter 11 of the text.
- [Min Weight Independent Set in a Grid Graph; 5 points] Problem 10 in Chapter
11 of the text.