3
$\begingroup$

Consider the standard minimum-cost flow problem presented here. I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and the target $t$) as follows: $$\sum\limits_{w \in V } {f({v_i},w) = \sum\limits_{w \in V} {f(w,{v_i}) = } {r_i}} ,\forall {v_i} \in V - \{ s,t\},$$ where $r_i$ is called vertex $v_i$ flow requirement (is there a standard term for it?). Please note that this problem is single-commodity and it is different from the multi-commodity flow problem.

Moreover, consider that all the capacities, costs, flows, and requirements are non-negative integers. Is there a well-known algorithm to solve this problem in polynomial time? If this is an NP-Complete problem, what's the fastest known algorithm and the approximation method to solve it?

Improve this question
$\endgroup$
4
  • $\begingroup$ I was thinking of duplicating every intermediate node $v_i$ to $v_i^1$ and $v_i^2$ and adding an edge from the former one to the latter one and setting the capacity of the edge as $d_i$ and the cost as a large negative number which is actually a reward for maximizing the flow to the original node. Does this idea work especially because of adding a negative cost? $\endgroup$
    – Javad
    Commented May 17, 2013 at 2:34
  • 4
    $\begingroup$ It's possible to solve this problem using Linear Programming. E.g., by duplicating vertices (as in your comment), and connecting t to s, you can restate this problem as a min cost circulation problem, in which the amount of flow on every edge is bounded from above and below. The set of such circulations forms an integral polytope. Thus LP will give you an integral solution. $\endgroup$
    – Yury
    Commented May 17, 2013 at 3:09
  • $\begingroup$ @JɛffE, I'm not sure what you mean. I suggest to solve the problem directly using LP. Note that the question asks to find an integral solution if “capacities, costs, flows, and requirements are non-negative integers” (this is not my assumption). I argue that the LP finds an integral solution since the circulation polytope is integral. However, since this fact is well-known for a more standard version where only edges have capacities, I transform the problem to this form. $\endgroup$
    – Yury
    Commented May 18, 2013 at 3:29
  • $\begingroup$ Sorry, I misunderstood "duplicate" as the standard trick of replacing an edge with capacity k with k unit-capacity edges. That won't work efficiently if k is exponential in n. But it isn't necessary to recast the problem as min cost circulation to get an LP; you just have to write it down. Directly. $\endgroup$
    – Jeffε
    Commented May 18, 2013 at 10:29

1 Answer 1

Reset to default
2
$\begingroup$

This is a standard variant (if not the standard variant) of the minimum-cost flow problem. The "flow requirements" are sometimes called balance conditions and sometimes called vertex supplies/demands. It can be solved in polynomial time using any number of algorithms.

In particular, you can reduce to the single-source single-target variant in polynomial time as follows:

  • Compute a conservative upper bound $M$ on the cost of any flow in your network; for example, let $M = \sum_e cap(e)\cdot |cost(e)|$. Alternatively, treat $M$ as a symbolic infinite value.
  • Add new nodes $s^*$ and $t^*$.
  • Add arcs $s^*\to s$ and $t\to t^*$ with infinite capacity and zero cost.
  • For every node $v_i$ with $r_i>0$, add an arc $s^*\to v_i$ with capacity $r_i$ and cost $-M$.
  • For every node $v_i$ with $r_i<0$, add an arc $v_i\to t^*$ with capacity $-r_i$ and cost $-M$.
  • Set all vertex requirements to zero.

The minimum-cost feasible flow from $s^*$ to $t^*$ in this modified network saturates every arc $s^*\to v_i$ and $v_i\to t^*$, and the remaining arcs carry the minimum-cost flow from from $s$ to $t$ in the original network that meets all the flow requirements.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am not sure about the reduction to the original problem. This solution seems to just inject some required flow externally. If $s^*$ and $t^*$ are removed, the saturation effect for every node will be gone and also the flow conservation will not be held any more because an incoming flow of $r_i$ is removed from every node. $\endgroup$
    – Javad
    Commented May 18, 2013 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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