<p>While I can't give you a name, I can provide evidence that the problem is <span class="math-container">$\mathbf{NP}$</span>-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). </p>

<p>Indeed, consider the <span class="math-container">$\mathbf{NP}$</span>-hard instance of the problem you have in mind, with source <span class="math-container">$s$</span> and destination <span class="math-container">$t$</span>. Via standard arguments, there is a corresponding <span class="math-container">$\mathbf{NP}$</span>-hard <em>decision</em> problem, of the form "is it possible to route at least <span class="math-container">$k$</span> units of flow from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>"? I'll assume here that <span class="math-container">$k$</span> 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.</p>

<p>Let <span class="math-container">$u$</span> denote the maximum (unrestricted) flow routable from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>, which is an upper bound for the solution to your problem. Further, let <span class="math-container">$t'$</span> be a new vertex you tack onto the graph. For every possible value in the set <span class="math-container">$Q = \left(\{k, k+1, k+2, k+3, \cdots, 2k-1\} \cup \{2k, 4k, 8k, 16k, \cdots \}\right)$</span> no larger than <span class="math-container">$u$</span>, add a parallel edge with that capacity from <span class="math-container">$t$</span> to <span class="math-container">$t'$</span>. 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.</p>

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

<p>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 <span class="math-container">$0$</span> from that  where it's at least some <span class="math-container">$k &gt; 0$</span>, and thus there is no multiplicative approximation. Standard modifications to this argument rule out additive (polynomial) approximations as well.</p>

<p>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.</p>

CC BY-SA 4.0
2018-10-26T16:47:52.863Z
2018-10-27T06:27:43.273Z
2018-10-27T06:27:43.273Z
Yonatan N
<p>I have a problem where I want to find the maximum flow from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>, such that, for an edge <span class="math-container">$e \in E$</span>, <span class="math-container">$f(e) = 0$</span> or <span class="math-container">$f(e) = c(e)$</span>. Where <span class="math-container">$f(e)$</span> is the flow in the edge and <span class="math-container">$c(e)$</span> its capacity. Basically, if a solution uses an edge, this edge is saturated.</p>

<p>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.</p>

<p>Thanks!</p>

<max-flow>
All-or-Nothing Single-Sink Flow Problem
Matheus Jun Ota
# All-or-Nothing Single-Sink Flow Problem

(Asked by: username_0 on 2018-10-26)

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!

**Tags:** max-flow

---

## 1 answers

### Answer by username_1 on 2018-10-26. Score: 6

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.


---

