Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?
share|improve this question
    
Just to be clear, is it a min-cost-max-flow problem, or a min-cost flow problem, where a certain amount of flow needs to be sent in the cheapest possible way? –  Paresh Dec 26 '12 at 22:55
    
It's a min-cost-max-flow Problem. Updated my question. –  Patrick Schmidt Dec 26 '12 at 23:02
1  
May I ask what was the original problem that you mapped into a flow network with these restrictions? I ask because there is a simple alternative solution, and I just want to make sure that that was not the original algorithm you are trying to map to max-flow. –  Paresh Dec 26 '12 at 23:19
1  
Does that mean there is only one vertex where this condition of only 1 outgoing edge receiving flow needs to be enforced? Or is this limitation for all vertices (in which case my answer should provide you with the simplest solution)? Also, I did not quite understand how you modeled your problem into the above construction. –  Paresh Dec 27 '12 at 1:03
1  
Flow problems that constrain flows to be paths are usually referred to as "unsplittable flows". Min-cost unsplittable flow is NP-Hard in general. However, that version has demands over edges, which your version lacks. –  Nicholas Mancuso Dec 27 '12 at 23:05
show 4 more comments

4 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Thanks, but since I want to apply the rule to a subset of vertices the solution won't be that simple. –  Patrick Schmidt Dec 28 '12 at 12:49
add comment

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.

share|improve this answer
add comment

In general, the answer is unknown!, no 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)

share|improve this answer
3  
Please complete your answer with references and more details. –  vonbrand Mar 3 '13 at 17:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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