XOR-like behavior in flow networks

Question

XOR is not the correct name, but I am looking for some kind of exclusive behavior.

I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-flow algorithm. Flow networks are quite handy because a lot of problems can be reduced to them in an easy and understandable way. In my case these are matchings with some additional constraints. As these constraints are getting more complex I've been wondering if there are some existing constructions to model specific behaviors.

In this case I want to restrict the outgoing flow of a node to a single edge.

Given a graph $G=(V, E)$, integral capacities $c(u,v)$ and costs $k(u,v)$. An arbitrary node is called $A$. It's direct neighbors are called $B_1, ..B_n$. Can we replace the edges $AB_1,...AB_n$ (red) with some construction so that only one edge can receive flow? Which means that if $AB_1$ gets some flow (e.g. $5/10$) no other (red) edge can receive flow.

We could add intermediate nodes/edges and play with costs and capacities. The total capacity of our new construction has to stay the same and the cost of the different alternatives have to stay somehow proportional.

So my questions are:

1. Are there constructions like this in general? (Any keywords, links, papers)
2. Can you suggest a solution to my specific problem?

Answer 1

In general, the answer is no. If we put XOR-like restrictions on the out-going edges of a vertex, we can prove that finding a min-cut-max-flow is NP-Hard. The technique is to reduce 3-SAT to it.

Let's assume there are $n$ variables $x_1, x_2, ..., x_n$ in the 3-SAT and $m$ clauses $c_1, c_2, ..., c_m$. We create a graph $G(V,E)$ encoding the instance of the 3-SAT problem. For each variable $x_i$, we create a vertex $v_i$ connected to the source $s$ with an edge of $\infty$ capacity. Two more vertices $u_i, w_i$, which are connected to $v_i$, are created to represent $x_i$ taking the value 0 or 1 also with edges of capacity $\infty$.

For each of the clauses $c_i$, we create a vertex $o_i \in G$ corresponding to it and $o_i$ is connected to the variables or their negations in the clause with edges of capacity $1$. For example, if $c_i = (x_3 \lor x_4 \lor \neg x_5)$, we connect it to $u_3, u_4, w_5$ with edges of capacity. All $o_i$ are connected to the sink with edges of capacity 1.

Since $x_i$ and $\neg x_i$ cannot take the same value, we put the XOR restriction on edges $(v_i, u_i)$, $(v_i, w_i)$, $\forall i = 1,2,3,...,n$. It can be proved that there is a maximum flow of size $m$ if and only if the 3-SAT instance is satisfiable. Since the problem is trivially in $NP$ and the reduction is polynomial, we conclude the decision version of XOR restriction network flow is NP-Complete.

Answer 2

For your first question, I do not know any general techniques or rules of thumb that you can use to model arbitrary restrictions in flow networks. Most examples I have seen are generally based on some intuition about the nature of restrictions, and often at first seem arbitrary.

For your particular case, I have yet to come up with a good mapping to max-flow. However, I can suggest a simple alternative solution (you might have already figured that out): Depth First Search from source $s$.

As the flow is restricted to only one outgoing edge for every vertex, what you have is a path from the source to the target. This path satisfies the two properties that it can carry the maximum flow among any other paths from source $s$ to target $t$, and that it has the lowest cost among all such paths that could carry the same flow from $s$ to $t$.

• Start a DFS from the $s$
• As you go down the DFS, keep track of the current minimum capacity of all edges encountered thus far.
• Also keep track of the current total cost (path length) encountered so far.
• If $t$ is reached during the DFS, compare these two values with global values, and update the global values if necessary.
• Backtrack from $t$ and continue with the DFS.

Basically, you enumerate all paths from $s$ to $t$ using the DFS, and choose the one that satisfies your criteria of min-cost and max-flow. The DFS itself takes $O(|E|)$ time, which is more efficient than a max flow algorithm.

Answer 3

To build on Paresh's answer, if all the max capacities are one (and everything else is integer), you could also split each node into two so that node (n-) has all the in edges, node (n+) has all the out edges, and (n-) and (n+) are connected with an edge of max capacity 1. Solve this new min-cost network and you are done.

If the max capacities are not all one, then the problem is harder. You can formulate the problem as a MIP (Mixed Integer Program). The only integer constraints are the XOR constraints.

Fortunately, these can be modeled as Special Ordered Sets - type SOS1 (see http://en.wikipedia.org/wiki/Special_ordered_set). Most MIP solvers specifically represent SOS1 constraints and will handle them much more efficiently (sometimes you need to tell it, sometimes it will figure it out - check your solver docs).

Although the MIP will eventually converge to the optimum answer, for really large models, you may not have the time to wait for it to finish. Getting large MIPs to converge is often more art than engineering.

The next suggestion is a lot more work. You could use a min-cost-network solver as a subroutine and do you own branching on the XOR edges using SOS1 techniques. For example, on each branch, turn off the least-used 1/2 of the out edges, resolve the min-cost network (very fast), repeat until all the XOR constraints are satisfied.

You could prioritize the branching sequence by your own criteria (flow volume, volume X cost, reserved capacity, number of possible edges, etc.). By guiding the search yourself, you can hone in on the parts of the solution that are most important to you.

You don't indicate whether you always know whether your problem is feasible or not. If it is always feasible, you might be able to get away with a branching strategy that is "backtrack free", that is, you follow it like a heuristic.

If the problem is not guaranteed to be feasible, a MIP could go away forever. A heuristic based on the above may still be valuable to find a solution quickly with a relatively low number of violations.

Answer 4

In general, the answer is unknown, not impossible!

we conclude the decision version of XOR restriction network flow is NP-Complete. therefore (it's possible, we can do that) if and only if P=NP.