I have a flow question which I'm stumped on but seems like there should be an answer that I am not seeing.

Consider a network with a start $s$ and an end $t$ and a bipartite graph $L \cup R$. $s$ is connected to all vertices in $L$ via edges with capacity $1$. All vertices in $R$ are connected to $t$ via edges with capacity $C$ where the only constraint on $C$ is that it's non-negative where $C> 0$. All vertices in $L$ are connected to exactly two vertices in $R$ via edges with capacity $\infty$. I want to check if there is a max flow of size $|L| = degree(s)$. I don't want to find the max flow if such a flow does not exist; I just want to check whether the max flow has this size.

Even if this is solvable for larger $C$ and not constant $C$ such as $C = \text{poly}\log n$, this would still be quite useful to me.

Can I do this in linear or near-linear $O(n \cdot polylog(n))$ time? It seems like it may be plausible. If so, I'd greatly appreciate knowing the algorithm.

  • $\begingroup$ Yes you're correct, if the graph was two regular, then we can verify using an Euler Tour but this is not a two regular graph. So it may not be simple to even get a perfect matching. My original question still stands though. $\endgroup$ Sep 12, 2022 at 2:08


Your Answer

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