I have a problem where I want to find the maximum flow from $s$ to $t$, such that, for an edge $e \in E$, $f(e) = 0$ or $f(e) = c(e)$. Where $f(e)$ is the flow in the edge and $c(e)$ its capacity. Basically, if a solution uses an edge, this edge is saturated.

I know this is an NP-hard problem, but I would like to know if there is any similar problem in the literature. Searching on Google I could only find algorithms for the All-or-Nothing Multicommodity flow problem, but I guess that my problem is simpler. I don't need to solve this optimally, approximation algorithms or heuristics are fine.



1 Answer 1


While I can't give you a name, I can provide evidence that the problem is $\mathbf{NP}$-hard to approximate to any factor, and thus is likely to be unstudied in full generality in the literature (hinting that it may remain unnamed).

Indeed, consider the $\mathbf{NP}$-hard instance of the problem you have in mind, with source $s$ and destination $t$. Via standard arguments, there is a corresponding $\mathbf{NP}$-hard decision problem, of the form "is it possible to route at least $k$ units of flow from $s$ to $t$"? I'll assume here that $k$ is polynomial, since that seems to be the case for most reductions I can think of (such as the one through Max-3D-matching). We begin with this problem to construct our inapproximable example.

Let $u$ denote the maximum (unrestricted) flow routable from $s$ to $t$, which is an upper bound for the solution to your problem. Further, let $t'$ be a new vertex you tack onto the graph. For every possible value in the set $Q = \left(\{k, k+1, k+2, k+3, \cdots, 2k-1\} \cup \{2k, 4k, 8k, 16k, \cdots \}\right)$ no larger than $u$, add a parallel edge with that capacity from $t$ to $t'$. While this transforms your graph into a multigraph (we will fix this later), the number of parallel edges we added here is at most polynomial.

If the original problem had a solution with value $\geq k$, then there is some amount of flow routable from $s$ to $t'$. Indeed, route that flow to $t$, decompose the amount of flow at $t$ into a sum of values in $Q$, and then route it along the corresponding edges. Otherwise, it is impossible to route any flow between $t$ and $t'$, and thus the maximum flow routable (in your set up) from $s$ to $t'$ is $0$.

Since the dependency on parallel edges can be removed by subdividing each edge with a vertex, we conclude that it's impossible to distinguish cases where the optimal solution has value $0$ from that where it's at least some $k > 0$, and thus there is no multiplicative approximation. Standard modifications to this argument rule out additive (polynomial) approximations as well.

As a side note, this approach is pretty thematic in proving such hardness results, and in general problems that can encode an all-or-nothing "all solutions must be of size at least X" constraint for arbitrary X tend to be very inapproximable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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