Max flow: either saturate an edge or avoids 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))$.