<p><strong>SHORT ANSWER</strong></p>
<p>Probably not, or at least a solution running in such a time is not known to this date.</p>
<p><strong>ARGUMENT</strong></p>
<p>According to <a href="https://en.wikipedia.org/wiki/Maximum_flow_problem" rel="nofollow noreferrer">Wikipedia</a>'s review of <a href="https://arxiv.org/abs/2203.00671" rel="nofollow noreferrer">Chen et al.</a>'s article on arXiv,
the ultimate state of the art on <code>Max Flow</code> is an algorithm computing the exact value of the maximal flow  in time within <span class="math-container">$O (m^{1+o(1)})$</span>. This should be taken with some moderate skepticism as it was not validated by a peer review system yet, but give an indication of the kind of results that the community is currently aiming for.</p>
<p>Since <span class="math-container">$m\in O(n^2)$</span>, the existence of an algorithm deciding if <code>MAX FLOW&lt;X</code> in time within  <span class="math-container">$O((m+n) \text{poly}\log n)$</span> implies the existence  of one running in time within <span class="math-container">$O(m \text{poly}\log m)$</span>, which would be even faster than <span class="math-container">$O (m^{1+o(1)})$</span> (because <span class="math-container">$O(\text{poly}\log m) \subset O(m^{o(1)})$</span>).</p>
<p>Hence, it seems that an algorithm deciding <code>Max Flow</code> running in time <span class="math-container">$O((m+n) \text{poly}\log n)$</span> is not known (yet).</p>
<p>Hope it helps!</p>

CC BY-SA 4.0
2022-09-12T11:22:37.443Z
2022-09-12T11:22:37.443Z
J.y B.y
<p>In a given network, is it possible to find a flow of value that is lower bounded by <span class="math-container">$X$</span> in near-linear time, <span class="math-container">$O((m + n) \text{poly}\log n)$</span>? I do not want to find the exact maximum flow just whether the flow is lower bounded by <span class="math-container">$X$</span>. If one can do this, what is the procedure for finding whether the maximum flow is indeed bounded by this value?</p>

CC BY-SA 4.0
2022-09-12T00:35:40.130Z
I can't understand the question.  What is $X$?  Please define all notation before first use of it.
D.W.
CC BY-SA 4.0
2022-09-12T00:38:54.513Z
If you're asking: given $X$, determine whether there exists a flow of value $\ge X$; then any algorithm to solve that question can be turned into one that finds the value of the max flow, using log many iterations of binary search.  It seems hard to imagine that it is significantly easier to find the value of the max flow, then to find the flow itself.  I wouldn't be surprised if there are straightforward reductions to show that if you can find the value of the max flow, you can construct a max flow.
D.W.
<ds.algorithms><max-flow-min-cut><max-flow>
Flow of value lower bounded by $X$
user14389379
# Flow of value lower bounded by $X$

(Asked by: username_0 on 2022-09-11)

In a given network, is it possible to find a flow of value that is lower bounded by $X$ in near-linear time, $O((m + n) \text{poly}\log n)$? I do not want to find the exact maximum flow just whether the flow is lower bounded by $X$. If one can do this, what is the procedure for finding whether the maximum flow is indeed bounded by this value?

**Tags:** ds.algorithms, max-flow-min-cut, max-flow

> **Comments:**
> **username_1**: I can't understand the question.  What is $X$?  Please define all notation before first use of it.  
> **username_1**: If you're asking: given $X$, determine whether there exists a flow of value $\ge X$; then any algorithm to solve that question can be turned into one that finds the value of the max flow, using log many iterations of binary search.  It seems hard to imagine that it is significantly easier to find the value of the max flow, then to find the flow itself.  I wouldn't be surprised if there are straightforward reductions to show that if you can find the value of the max flow, you can construct a max flow.  

---

## 1 answers

### Answer by username_2 on 2022-09-12. Score: 0

**SHORT ANSWER**

Probably not, or at least a solution running in such a time is not known to this date.

**ARGUMENT**

According to [Wikipedia](https://en.wikipedia.org/wiki/Maximum_flow_problem)'s review of [Chen et al.](https://arxiv.org/abs/2203.00671)'s article on arXiv,
the ultimate state of the art on `Max Flow` is an algorithm computing the exact value of the maximal flow in time within $O (m^{1+o(1)})$. This should be taken with some moderate skepticism as it was not validated by a peer review system yet, but give an indication of the kind of results that the community is currently aiming for.

Since $m\in O(n^2)$, the existence of an algorithm deciding if `MAX FLOW in time within $O((m+n) \text{poly}\log n)$ implies the existence of one running in time within $O(m \text{poly}\log m)$, which would be even faster than $O (m^{1+o(1)})$ (because $O(\text{poly}\log m) \subset O(m^{o(1)})$).`

Hence, it seems that an algorithm deciding `Max Flow` running in time $O((m+n) \text{poly}\log n)$ is not known (yet).

Hope it helps!


---

