  


The Maximum Flow Problem with Disjunctive Constraints
Ulrich Pferschy(pferschyunigraz.at) Abstract: We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at least one arc has to carry flow in a feasible solution. It is convenient to represent the negative disjunctive constraints in terms of a socalled conflict graph whose vertices correspond to the arcs of the underlying graph, and whose edges encode the constraints. Analogously we represent the positive disjunctive constraints by a socalled forcing graph. For conflict graphs we prove that the maximum flow problem is strongly NPhard, even if every connected component of the conflict graph is a path of length two. In contrast to this we show that for forcing graphs the problem can be solved efficiently if fractional flow values are allowed. If on the other hand the flow values are required to be integral we provide the sharp line between polynomially solvable and strongly NPhard instances. Keywords: maximum flow problem, conflict graph, binary constraints Category 1: Combinatorial Optimization (Graphs and Matroids ) Category 2: Network Optimization Citation: Download: [PDF] Entry Submitted: 01/20/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  