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?

  • $\begingroup$ Interesting problem! There's an obvious adaptation to the Ford-Fulkerson algorithm: rather than searching for any augmenting path from $s$ to $t$ in the residual graph, search specifically for one where all edges traversed have the same capacity (i.e., where pushing flow along that path will saturate all of those edges and thus be consistent with your all-or-nothing constraint). Have you tried checking whether this leads to a valid, polynomial-time algorithm for your problem? $\endgroup$ – D.W. Dec 19 '15 at 21:14

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


Consider the following decision problem.

Determine if the network N has a flow of size at least k, but with the restriction that some (fixed pre-determined) edges must either have 0 flow, or be at maximal capacity.

This problem is NP-complete, I have a proof written up here (arxiv).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.