3
$\begingroup$

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!

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 18 '13 at 17:00
  • $\begingroup$ 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. $\endgroup$ – Andrew Baker Nov 18 '13 at 17:38
  • $\begingroup$ 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. $\endgroup$ – Yoshio Okamoto Nov 19 '13 at 6:49
  • 3
    $\begingroup$ Your problem would most likely be NP-Complete/NP-Hard. You should state the problem more precisely. $\endgroup$ – Chandra Chekuri Nov 19 '13 at 15:50
  • $\begingroup$ @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. $\endgroup$ – Andrew Baker Nov 19 '13 at 18:39
1
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.