Optimization Online


The Maximum Flow Problem with Disjunctive Constraints

Ulrich Pferschy(pferschy***at***uni-graz.at)
Joachim Schauer(joachim.schauer***at***uni-graz.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 so-called 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 so-called forcing graph. For conflict graphs we prove that the maximum flow problem is strongly NP-hard, 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 NP-hard instances.

Keywords: maximum flow problem, conflict graph, binary constraints

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Network Optimization


Download: [PDF]

Entry Submitted: 01/20/2010
Entry Accepted: 01/20/2010
Entry Last Modified: 01/20/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society