1
$\begingroup$

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of all edges is always an integer, and so is the flow. Is there an algorithm that can find a maximum flow in this new network with complexity O(|E|), where E is the set of edges? If so, what would this algorithm look like?

$\endgroup$
0
$\begingroup$

Since you only have $7$ edges (and hence at most $8$ vertices reachable from the flow source) any flow algorithm whose runtime is independent of the edge weights will take time $O(1) = O(|E|)$. See, for example, the Edmonds-Karp algorithm.

$\endgroup$
8
  • $\begingroup$ Why are there at most 8 vertices reachable from the flow source? $\endgroup$
    – cyberspace
    Oct 12 '21 at 10:15
  • $\begingroup$ Consider the undirected version of your input network. The number of edges in this network is at most $7$ by hypothesis. Consider the connected component $C$ containing the source. Pick any spanning tree $T$ of $C$. The number of edges in the tree is a lower bound to the number of edges in $C$. A tree with $n$ vertices has exactly $n-1$ edges. Therefore if $C$ has $9$ or more vertices, then $T$ has 8 edges, and both $C$ and the input network contain at least $8$ edges. $\endgroup$
    – Steven
    Oct 12 '21 at 10:43
  • $\begingroup$ I forgot to mention that the edges are directed. I have edited the question. Since it is not given that the graph is connected, can we still use the same reasoning? $\endgroup$
    – cyberspace
    Oct 12 '21 at 10:50
  • $\begingroup$ My answer (and my previous comment) works regardless of whether the graph is directed or undirected. Also, I never assumed that the graph was connected. $\endgroup$
    – Steven
    Oct 12 '21 at 10:53
  • $\begingroup$ Then how can we assume that there exists a component $C$ in a graph that is not connected? $\endgroup$
    – cyberspace
    Oct 12 '21 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.