6
$\begingroup$

I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient algorithms that solve this problem directly, so I am trying to think of a way to transform the problem so that it can be passed to standard max-flow algorithms that assume all arc capacities are non-negative.

The only hint I could find online was a question in a 1999 homework assignment which asks students to "Show how to reduce the problem of maximum flow with possibly negative capacities to two maximum flow problems both with nonnegative capacities." (The original can be seen here: http://www.cs.cmu.edu/afs/cs/academic/class/15750-s99/www/homeworks/hw4.ps )

How can this be done?

Edit #1: I should explain the origin of these ((u,v),(v,u)) pairs. What I am really trying to do is solve an s-t maximum flow in a graph that is essentially undirected. By "essentially undirected" I mean a graph that is undirected except for arcs with source s and target in the undirected graph, and arcs with source in the undirected graph and target t. Of course, this kind of "partially directed" graph must be translated into a normal directed graph for any s-t max flow algorithm. To do this, I am applying the standard transformation of replacing every undirected edge (u<->v) (with weight c) with a pair of directed arcs (u->v) and (v->u) with weight c. Since the original graph sometimes has negative edge weights, these ((u,v),(v,u)) pairs with equal negative weights arise.

$\endgroup$
3
  • $\begingroup$ Can you clarify the problem? I assume that an arc with capacity -7 needs to have a flow of -7 or less, right? But can an arc with positive capacity get a negative flow? $\endgroup$ Mar 26, 2011 at 8:17
  • 1
    $\begingroup$ Ok, I have just read the problem in the link. Still not so clear. If you have an arc pair $\{(u,v),(v,u)\}$, both with the same negative capacity, what would be an admissible flow on these arcs? Or is one capacity positive and the other negative, of the same absolute value, so that you essentially specify your flow at this arc? $\endgroup$ Mar 26, 2011 at 8:21
  • 2
    $\begingroup$ If arcs ${(u,v),(v,u)}$ both have capacities of -7, isn't this the same as saying that both arcs must have positive flows of at least 7 units? $\endgroup$ Mar 26, 2011 at 14:20

3 Answers 3

4
$\begingroup$

The correspondence between max flow with lower capacities and max flow with negative capacities as described in the linked homework problem is based on the convention that $f(u,v)=-f(v,u)$ for all arc pairs $\{(u,v),(v,u)\}$. http://computingscience.nl/docs/vakken/an/an-maxflow.ppt contains a reduction of max flow with lower capacities to the solution of two standard max flow problems, thus solving the homework question. If I understand your problem correctly, it is a bit more complicated: A weight of $-7$ on an (undirected) edge $\{u,v\}$ means that you want to send at least 7 units of flow either from $u$ to $v$ or from $v$ to $u$. As far as I can see, for this problem the standard transformation of replacing the edge by an arc pair does not work. In the standard case only one of the arcs $(u,v)$ and $(v,u)$ is used in an optimal solution, and its flow value can be used as the value for the undirected edge. But how would you transfer $f(u,v)=-9$, $f(v,u)=-12$ back to the undirected model?

Practically, the first thing I would try is to write the original problem as a mixed integer program (I guess you have to model the choices for the arc directions with binary variables) and throw it into a general purpose solver (Cplex, Gurobi, http://zibopt.zib.de, http://www.coin-or.org/ ).

$\endgroup$
2
$\begingroup$

Thanks everyone for your comments. Unfortunately, I now realize that I was trying to do the impossible. As Brian's comment suggests, I can't have a net flow of +7 in both directions between a pair of nodes. As Kali points out, a choice must be made at every such arc-pair that leads to a combinatorial explosion.

I came to the realization yesterday: by the duality of max-flow and min-cut, if I could solve a max-flow problem with negative edge weights then I could solve a min-cut problem with negative edge weights. However, since I can translate any (NP-complete) max-cut problem into a min-cut problem by negating all the edge weights, I can't expect to solve such problems in P-time.

I see now (thanks to Kali) that the homework question makes the (standard) assumption of what I think is called "skew symmetry". The problem I have is incompatible with this and therefore isn't merely a network flow problem with negative edge weights.

$\endgroup$
3
  • $\begingroup$ If you are just interested in the solution to your problem (and not in obtaining it by a provably polynomial algorithm) I still recommend to simply try solving the MIP. $\endgroup$ Mar 28, 2011 at 1:33
  • $\begingroup$ Yes, I will probably do this. Since the negative capacity edge pairs are static and reasonably limited in number, an MIP solver is probably going to do a reasonable job. I can also make use of suboptimal solutions, so I agree it is a good way forward. $\endgroup$
    – Fumiyo Eda
    Mar 28, 2011 at 6:26
  • $\begingroup$ @Fumiyo, What did you end up doing? I have been working on this problem to come to the same conclusion you did regarding the incompatibility of negative undirected weights with the standard "skew symmetry" assumption. I suspected from the beginning this problem would be NP-hard. Did you find a good approximation? $\endgroup$ May 3, 2014 at 6:21
1
$\begingroup$

The problem you describe sounds like an energy minimization on a Markov Random Field (MRF).

Min E = sum[D(p)] + sum[V(p,q)]

where p, q is a binary labelling = {sink=0, source=1}.

The first term of E sums over all the nodes in the undirected graph. D(p=0) is the weight on the source-to-node edge and D(p=1) the weight on the node-to-sink edge.

The second term of E sums over all edges in the undirected graph, where p is the label on one end of the edge and q the label on the other end.

The standard min-cut with positive weights correponds to: V(0,0)=V(1,1)=0 and V(0,1)=V(1,0)=weight. More general, if V(p,q) satisfies the submodular condition on all edges, then minimizing E is the same as an s-t max-flow\min-cut.

Submodular: V(0,1) + V(1,0) >= V(0,0) + V(1,1)

If there are (some) negative weighted edges, these do not satisfy submodularity. Instead they are supermodular.

Supermodular: V(0,1) + V(1,0) <= V(0,0) + V(1,1)

If all edges are supermodular, I guess there is an equivalence with max-cut.

However, the problem you describe coontains a mixture of submodular (positive weighted) and supermodular (negative weighted) edges. This is indeed NP-hard. But how to solve it? You might consider looking into Quadratic Pseudo Boolean Optimization (QPBO): Wikipedia

$\endgroup$

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.