Homework 4
Algorithms and Data
Spring 2012
Karl Lieberherr
Due date:
Feb. 8, 2012, beginning of class.
Read Chapter 3 in the text book again.
By now you should have covered chapters 1 through 3.
This homework covers two exercises from chapter 3.
PART 1:
A generalization of Kleinberg Chapter 3, Ex 9:
Claim:
Let c be an integer > 1.
Suppose that an n-node undirected graph G=(V,E),
where |V|=n is a multiple of c,
contains two nodes s and t such that the distance
between s and t is strictly greater than n/c.
Show that there must exist
a set DIS of AT MOST c-1 nodes v_1, v_2, ..., v_c-1,
not equal to either s or t, such that deleting all nodes
in DIS from G destroys all s-t paths.
Give an algorithm with running time O(m+n)
to find set DIS.
We assume that c is a constant.
Expressed with quantifiers:
claim Graph-DIS(Name,c):
ForAll undirected graphs G=(V,E), |V|>c,
such that Exists s,t in V: dist(s,t)>|V|/c
Exists set DIS of c-1 nodes v_1, v_2, ... ,v_c-1 in V
such that G'=(V-DIS,E - edges incident with nodes in DIS) has
no s-t path
ForAllP provides the triple (G,s,t) such that dist(s,t)>|V|/c.
ExistsP solves for DIS with above property.
What is interesting about this problem is that the
brute-force solution has running time O(n^(c-1) * (n+m)).
We enumerate all subsets of AT MOST size c-1, which is O(n^(c-1)),
and for each such set we delete its node from the graph
and we check whether there is a path from s to t
which is O(m+n).
It is a common theme in algorithm design that when we have
additional information, we might successfully take advantage
of it. Here the additional information is that there is
a path of length > n/c from s to t. It is an art
to figure out how the additional information can
be exploitet.
We are playing this game on Piazza in the usual way
by having 5 claims in public and carrying out the refutation
protocol in public (to agree/defend or refute).
There is no strengthening because this is
not an optimization problem.
The claims to be put on Piazza must have a c between 2
and 10. ForAllP must give a graph with between
100 and 200 nodes
which means that proposer and opposer must have
an implementation to play the game effectively.
If this is too much work, use smaller instances.
We define a JSON language to define
instances and solutions.
Instance
{"graph-with-s-t" : G, "s" : 0, "t" : 9}
where G is the JSON notation for undirected graphs.
See:
http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp12/JSON/graphs-in-JSON
Solution
{"set" : [1,2,3,7,9]}
PART 2:
=================================================
Answer exercise 12, chapter 3, page 112.
What to turn in:
For part 1:
1) Your algorithm for computing a solution (set of nodes
to be deleted) from an instance (a graph).
2 optional) Your algorithm for generating instances (graphs for claim Graph-DIS(c)).
3) An argument why your algorithm from (1) works correctly.
Ideally you submit an implementation of your algorithms in
your favorite programming language.
For part 2:
Your description of how to translate the concrete problem
into an algorithmic problem and how to solve it and map the solution
back to the concrete problem.