# Maximum flow in integer flow network

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?

• Is the 7 an accident in this question? Or does your graph really have only 7 edges? The question is interesting (but with answer not as far as we know) if you simply drop 7 from the question. Nov 6, 2022 at 19:32

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.
• 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. Oct 12, 2021 at 10:43
• Then how can we assume that there exists a component $C$ in a graph that is not connected? Oct 12, 2021 at 10:56
In case the 7 was entered accidentally, and the question was whether a max flow can be computed in time $$O(m)$$ provided that we have a max flow already, and simply increase all capacities by one.
The answer is that the best max flow algorithm is $$\omega(m)$$ for graphs of unit capacities, which means that if you start out with only capacity $$0$$ for your graph, the empty flow $$f \colon e \mapsto 0$$ is a max flow. Then if you increase all capacities with 1, you have a unit capacity flow network. An algorithm with time $$O(m)$$ would be a ground-breaking achievement at this time (but still possible).