I am trying to find an algorithm which recieves as input: 1) a Flow network N(G,c,s,t) in which the capacity of an edge is either 0 or 1 (i.e. Exists or not). 2) a positive integer k
The output should be a set of k edges from G so that removing them (reducing their capacity to 0) will create a flow network with a minimal "max-flow" as possible.
After mauling it over for the last 3 hours, I am thinking it has to do with reducing those edges that are involved in the min-cut. Still I am not able to formulate an algorithm that of which correctness i can prove.
Thank you for any help in directing me to an answer.
EDIT: After further thought, I have found the min-cut edges by following this: (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow)
If i remove an edge that belongs to tthe min cut, i create a smaller cut and therefore a small flow (min-cut=max-flow).
If K>=(number of edges in the cut) then the flow will be 0, otherwise the flow will be the number of edges minus k.
Does that sound good? Do i need to prove something other than the correctness of min-cut=max-flow?