Homework #7 Introduction to Algorithms

Homework #7
Introduction to Algorithms
601.433/633

Problem 1 (15 points)
For a directed graph G = (V, E) (source and sink in V denoted by s and t respectively) with capacities c : E → R
+, and a flow f : E → R
+, the support of the
flow f on G is the set of edges Esupp := {e ∈ E | f(e) 0}, i.e. the edges on
which the flow function is positive.
Show that for any directed graph G = (V, E) with non-negative capacities c :
E → R
+ there always exists a maximum flow f
∗
: E → R
+ whose support has
no directed cycle.
Hint: Proof by contradiction?
Problem 2 (20 points)
In a graph G = (V, E), a matching is a subset of the edges M ⊆ E such that no
two edges in M share an end-point (i.e. incident on the same vertex).
Write a linear program that, given a bipartite graph G = (V1, V2, E), solves the
maximum-bipartite-matching problem. I.e. The LP, when solved, should find the
largest possible matching on the graph G.
Clearly mention the variables, constraints and the objective function. Prove why
1
the solution to your LP solves the maximum-bipartite-matching problem. You may
assume that all variables in the solution to your LP has integer values.
Problem 3 (15 points)
In class you saw that VERTEX-COVER and INDEPENDENT-SET are related problems. Specifically, a graph G = (V, E) has a vertex-cover of size k if and only if
it has an independent-set of size |V | − k.
We also know that there is a polynomial-time 2-approximation algorithm for VERTEXCOVER. Does this relationship imply that there is a polynomial-time approximation algorithm with a constant approximation ratio for INDEPENDENT-SET? Justify your answer.
Problem 4 (10 points)
You are given a biased coin c but you dont know what the bias is. I.e. the coin c
outputs H with probability p ∈ (0, 1) (note that it is not inclusive of 0 and 1) and T
with probability 1 − p every time you toss it but you don’t know what p is.
Can you simulate a fair coin using by tossing c? I.e. Come up with a “rule” for
tossing c (possible several times) and outputting H or T based on the output of
the coin tosses of c such that you will output H with probability 1/2 and T with
probability 1/2? Please prove the correctness of your solution.
Hint: i) What if you had two coins c1, c2 with the same bias instead of one? Can
you toss them together and output H or T based on the output? ii) You shouldn’t
be trying to “estimate” p.
2