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?
2
-
$\begingroup$ I can't understand the question. What is $X$? Please define all notation before first use of it. $\endgroup$– D.W.Sep 12, 2022 at 0:35
-
2$\begingroup$ 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. $\endgroup$– D.W.Sep 12, 2022 at 0:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
SHORT ANSWER
Probably not, or at least a solution running in such a time is not known to this date.
ARGUMENT
According to Wikipedia's review of Chen et al.'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<X 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!
