Q:

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?

A:

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))$.

