Question 1

Hint: design a linear-time subroutine that takes a real-number T and determines if there is a path from s to t of bottleneck capacity greater than or equal to T.



Question 2

Hint: formulate the bipartite matching problem as a maxflow problem; find a (fractional) feasible flow of value n; conclude that there is a perfect matching.



Question 3

Hint: formulate as a mincut problem; assign edge (v,w) a weight of infinity if there is an edge from v to w in the original digraph.