Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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.
