# Network Flow with Non-contiguous Capacities

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!

• 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. Nov 18 '13 at 17:00
• 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 Nov 18 '13 at 17:38
• 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 Nov 19 '13 at 6:49
• Your problem would most likely be NP-Complete/NP-Hard. You should state the problem more precisely. – Chandra Chekuri Nov 19 '13 at 15:50
• @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 Nov 19 '13 at 18:39

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.