1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\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$
    – user1246462
    Sep 12, 2022 at 2:08

0

Reset to default

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.