Optimally reducing maximum flow
- by ArIck
Given a parameter k, I'm trying to delete k edges from a directed graph such that the maximum flow is reduced by 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 proposed solution would be to first perform a topological sorting on the graph, using an algorithm that "forgives" cycles -- perhaps by ignoring edges that lead 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
Would this work, or am I totally off-track here?
