[Solved]: XOR-like behavior in flow networks

Problem Detail: 

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?

Asked By : Patrick Schmidt

Answered By : Strin

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7610