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$
1
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Nov 6, 2022 at 19:32

2 Answers 2

1
$\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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 10:56
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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