# All-or-Nothing Single-Sink Flow Problem

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.

Thanks!

## 1 Answer

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.