Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half through another edge.
Can this be formulated as a max flow problem with a polynomial time solution or is this problem hard?
This problem is NP-hard.
Reduction from PARTITION:
Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:
$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$ $$c((s,x_i))=c((x_i,v))=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$
$S$ is partitionable iff there exist "saturate edge or avoid" flow of value $c((v,t))$.
I wrote an algorithem that solve a bipartite with a lot of constrains and this was one of them. but to solve it i did not use a residual graph, and the solution is not very effective, but it's working good enough for my goals. I used capacity scalling algorithem and i disabled all the residual edges so the flow only push forward (without the ability to undo). and to compensate on cases in which the flow is not the maximum possible flow. i run this algorithem couple of times, each time suffeling the nodes in the graph. at the end i have choosen the solver that had the maximum flow. not sure about how good it solve non bipartite problem or a large one.
