<p>I think this is NP-complete, here I try to give a reduction from 1-in-3-SAT, where we want every clause to contain exactly one true literal. Suppose we are given a 3-CNF with $n$ variables and $m$ clauses, from this we construct a DAG.</p>

<p>The first level consists of the source $s$.</p>

<p>From here you have an edge of capacity $m$ to $v_i$ for each variable $x_i$.</p>

<p>The third level has vertices of the form $x_i$ and $\bar x_i$, with an edge of capacity $0$ or at least $m$ from the corresponding $v_i$.</p>

<p>On the fourth level, there is a vertex $c_j$ for every clause with an edge of capacity $0$ or at least $1$ from its literals. We also have an extra vertex, $w$ with edges of capacity $m$ from every literal vertex.</p>

<p>Finally, on the fifth level we have the target, $t$ with an edge of capacity $1$ from each $c_j$ and an edge of capacity $mn-m$ from $w$.</p>

<p>In this graph you have a flow of size $mn$ if and only if there is a 1-in-3-SAT assignment.</p>

CC BY-SA 3.0
2013-11-19T20:03:20.007Z
2013-11-19T20:03:20.007Z
domotorp
<p>I have a problem that I can model as a minimum cost network flow. The only problem is that I need to be able to set the flow through some arcs to be either 0 or at least 5. That is, the arc cannot carry an integer flow of 1 through 4, but is otherwise okay. Can anyone point me in the direction of any pre-existing work on a problem like this?</p>

<p>Thank you!</p>

CC BY-SA 3.0
2013-11-18T17:00:58.760Z
If this is a practical problem, you could try using integer linear programming (ILP).  There's no guarantee it will work efficiently on any particular problem, and you won't get any useful bounds/guarantees on its asymptotic running time, but existing ILP solvers are quite good and are able to solve many problems that you wouldn't think they'd be able to.
D.W.
CC BY-SA 3.0
2013-11-18T17:38:30.820Z
Yes, it is a practical problem, so I will look at ILP solvers. Bounds on the running time would be nice though. It will be an extremely large network, so speed is of the essence.
Andrew Baker
CC BY-SA 3.0
2013-11-19T06:49:43.270Z
I'm confused. An arc with capacity 0 means no flow can go through that arc. So I wonder if an arc with capacity 0 or at least 5 just means an arc with capacity at least 5.
Yoshio Okamoto
CC BY-SA 3.0
2013-11-19T15:50:47.800Z
Your problem would most likely be NP-Complete/NP-Hard. You should state the problem more precisely.
Chandra Chekuri
CC BY-SA 3.0
2013-11-19T18:39:47.350Z
@Yoshio, If we have a lower bound capacity of 5, then we must have a flow of at least 5 through that arc. It would not be a valid flow if nothing went through that arc. I also want to accept a flow of 0 through that arc. The idea is that if we have at least 5 flow going into node a, then we can use the {0,5+} arc to go to the sink t for low cost. Otherwise, we have to go to intermediate node b and then t for a higher cost. The problem is that always requiring a minimum capacity of 5 on arc (a,t) would mean the latter option would be a violation.

Chandra, I too fear it may be NP-something.
Andrew Baker
<max-flow>
Network Flow with Non-contiguous Capacities
Andrew Baker
# Network Flow with Non-contiguous Capacities

(Asked by: username_0 on 2013-11-18)

I have a problem that I can model as a minimum cost network flow. The only problem is that I need to be able to set the flow through some arcs to be either 0 or at least 5. That is, the arc cannot carry an integer flow of 1 through 4, but is otherwise okay. Can anyone point me in the direction of any pre-existing work on a problem like this?

Thank you!

**Tags:** max-flow
> **Comments:**
> **username_1**: If this is a practical problem, you could try using integer linear programming (ILP).  There's no guarantee it will work efficiently on any particular problem, and you won't get any useful bounds/guarantees on its asymptotic running time, but existing ILP solvers are quite good and are able to solve many problems that you wouldn't think they'd be able to.  
> **username_0**: Yes, it is a practical problem, so I will look at ILP solvers. Bounds on the running time would be nice though. It will be an extremely large network, so speed is of the essence.  
> **username_2**: I'm confused. An arc with capacity 0 means no flow can go through that arc. So I wonder if an arc with capacity 0 or at least 5 just means an arc with capacity at least 5.  
> **username_3**: Your problem would most likely be NP-Complete/NP-Hard. You should state the problem more precisely.  
> **username_0**: @Yoshio, If we have a lower bound capacity of 5, then we must have a flow of at least 5 through that arc. It would not be a valid flow if nothing went through that arc. I also want to accept a flow of 0 through that arc. The idea is that if we have at least 5 flow going into node a, then we can use the {0,5+} arc to go to the sink t for low cost. Otherwise, we have to go to intermediate node b and then t for a higher cost. The problem is that always requiring a minimum capacity of 5 on arc (a,t) would mean the latter option would be a violation.  Chandra, I too fear it may be NP-something.  

---

## 1 answers

### Answer by username_4 on 2013-11-19. Score: 1

I think this is NP-complete, here I try to give a reduction from 1-in-3-SAT, where we want every clause to contain exactly one true literal. Suppose we are given a 3-CNF with $n$ variables and $m$ clauses, from this we construct a DAG.

The first level consists of the source $s$.

From here you have an edge of capacity $m$ to $v\_i$ for each variable $x\_i$.

The third level has vertices of the form $x\_i$ and $\bar x\_i$, with an edge of capacity $0$ or at least $m$ from the corresponding $v\_i$.

On the fourth level, there is a vertex $c\_j$ for every clause with an edge of capacity $0$ or at least $1$ from its literals. We also have an extra vertex, $w$ with edges of capacity $m$ from every literal vertex.

Finally, on the fifth level we have the target, $t$ with an edge of capacity $1$ from each $c\_j$ and an edge of capacity $mn-m$ from $w$.

In this graph you have a flow of size $mn$ if and only if there is a 1-in-3-SAT assignment.


---

