maximum flow with all or nothing through each edge

Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the subset-sum problem, the capacities are small. Is this solvable in polynomial time or is it NP-Complete?

Your problem is NP-hard. There is a reduction from Independent Set to its decision version.

Consider an instance $G=(V,E)$ of Independent Set, you construct a network with vertices $\{s,t\}\cup V\cup V'$ where each vertex in $V'$ corresponds to a pair of vertices in $V$. For example, if $V=\{1,2,3\}$, then $V'=\{v_{12},v_{23},v_{13}\}$. Then we construct the edges as follows:

• For each vertex $x\in V$, add an edge $(s,x)$ with capacity $|V|-1$.

• For each vertex $v_{xy}\in V'$, add two edges $(x,v_{xy})$ and $(y,v_{xy})$. Both edges have capacity 1.

• For each vertex $v_{xy}\in V'$ where $(x,y)\in E$, add an edge $(v_{xy},t)$ with capacity 1.

• For each vertex $v_{xy}\in V'$ where $(x,y)\notin E$, add two edges $(v_{xy},t)$ with capacity 1 (if multiple edges are not allowed, we can add another two vertices $u_1,u_2$ and add two paths $v_{xy}\rightarrow u_1\rightarrow t$ and $v_{xy}\rightarrow u_2\rightarrow t$, which has the same effect).

Now $G$ has an independent set of size $k$ if and only if the constructed network has a flow of value $(|V|-1)k$.

StackExchange Computer Science Q#50932, answer score: 3