Description

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