Have Geek Brain

Optimal reduction of maximum flow

Given the parameter k, I am trying to remove k edges from the oriented graph in such a way that the maximum flow is reduced as much as possible. The graph has a source s and a sink t, and the capacity of each edge is one. The graph may or may not contain cycles.

My suggested solution would be to first perform a topological sort on the graph using an algorithm that "forgives" loops - perhaps ignoring the edges that take us back to the source. Then (assuming k> = 1):

i = 0
for each vertex u order by topological(u)
   for each edge (u, v) order by topological(v) descending
       if topological(v) > topological(u) then
            delete (u, v)
            if ++i = k then return
       else
            // edge doesn't contribute to max flow, ignore

Will this work or am I completely disconnected here?

+2


source to share


1 answer


I think you are completely out of the game. Your algorithm may not decrease the flow at all, whereas you can decrease the maximum flow by at least k (or make it 0).



Do you know the minimum flow maximum flow theorem?

+1


source






More articles:


All Articles