Homework #7 Introduction to Algorithms 601.433/633


5/5 - (2 votes)

Homework #7
Introduction to Algorithms

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
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.

Scroll to Top