$($a$)$ Let $G=\{V,(vec(E)),c_e,s,t,k\}$ be a flow network where $k$ is an integer and AAeinE,$c_e=1.$ Describe an

efficient algorithm to identify $k$ edges in $G$ such that after deleting those $k$ edges, the value of the

maximum $(s,t)-$flow in the remaining graph is as small as possible.

$($b$)$ Let $G=\{V,(vec(E)),c_e,s,t\}$ be a flow network. As we saw in class, a flow network can have more than

one min $(s,t)-$cut. Let's define the shortest min $(s,t)-$cut to be any minimum cut$(S,T)$ in the flow

network with the smallest number of edges crossing from $S$ to $T.$ Describe an efficient algorithm to

find the shortest min $(s,t)-$cut when $c_e$ are non$-$negative integers.

We expect: a clear description of your design in plain English, a justification of its correctness, and a

runtime analysis of its runtime. Big$-O$ notation is required.