Max flow problem

Motivation and basics can be found in the following lecture: click on this link

Flow problem allow to model a wide class of problems. They correspond to physical flows in a traffic/electric/gas grid. The problem is to forward the largest quantity of material from a source s to a destination t.

Definition

A network is an oriented graph N=(V,A) with a positive value on its arcs. Tje value c(x,y) on (x,y) is called the capacity. N have two specific nodes: a source s and a destination/sink t. Other vertices are called intermediate.

A flow is the quantity of material passing from a vertex to another. This quantity must be inferior or equal to the capacity of the arc. Furthermore, it is not possible to stock or to produce materials in intermediate vertices. A flow is similar to the laws of Kirchhoff.

A flow F in a network N have the two following properties:

  1. For all arc a ∈ A, 0F(a)c(a)
  2. For all intermediate vertex xV \ { s,t }, ∑y F(y,x) = ∑y F(x,y)

The sum F(x) =yF(y,x) is the incoming flow of vertex x
La somme F+(x) =yF(x,y) is the outcoming flow of vertex x
The value | F | for a flow F is defined as | F | = F+(s)F(s). In a basic flow problem, it’s equal to zero.

A flow problem

A basic flow problem is a linear problem. We suppose that between any couple of vertices it exists an arc. If an arc have no capacity, it is equal to zero. The objective function is the outcoming flow at the source or the incoming flow at the sink.

Constraints of a flow problem are as following:

  • Capacity: f(u,v) ≤ c(u,v)
  • Symmetry: f(u,v) = – f(v,u)
  • Flow conservation: | F |=0
  • etc.

Various industrial problems are similar to a flow problem or can be reduced to. A naive algorithm consists to repeat the following process until you get stuck. Find a s − t path where each arc has f (e) < u(e) and augment flow along it by the minimum of u(e) − f (e). This method does not give an optimal value, we need to be able to backtrack.

Problem’s reduction

Various problems can be reduced into max flow problem, for examples:

  • network connectivity: edge-disjoint paths, network reliability.
  • matching: bipartite matching, maximum matchings.
  • vertex capacities: data mining.
  • scheduling: airline scheduling, project selection.
  • graph cuts: image processing.
  • assignment: baseball elimination, distributed computing.

Multi-source multi-sinks: a parent source is linked to every sources and the capacity of each new arc verifies the flow conservation rule. Same with a parent sink.

Flow with max-min capacities: vertices are duplicated, the capacity of the new arc substitute the vertex’ capacity.

Shortest path: the source is the start and the sink is the end with d(s)=1 et d(t)=-1. There is no capacity’s constraints and the cost of each flow is equal. The problem become a min cost flow.

Cut and residual graph

A cut (E,T) of a graph N=(V,A) is a partition of V between E and T=V-E such as s ∈E and t∈T. We defined the capacity of the cut c(E,T) as the sum of the capacity of all arcs (u,v) with u in the set E and v in the set T. For any cut (E,T) and a flow f, |f| cannot exceeded c(E,T).
Delete a set of edges to disconnect t from s. Found a set to minimize the sum of edge’s capacity. A min-cut is a node partition (S,T) such that s is in S and t is in T where c(E,T) is minimal. By definition, min-cut problem have the same result that a max flow problem.
Taking N=(V,A) a graph and a flow f, we named residual capacity cf (u,v) = c(u,v) – f(u,v). If the capacity of (v,u) is zero, then cf (v,u) = f(u,v). A residual capacity is superior or equal to zero.

The residual graph N’=(V,A) is based on all residual capacity and the capacity minus the residual one. An augmenting path is a path in the residual graph.

residuel

From the residual graph of a max flow, it is possible to find the solution of min-cut problem (and vice versa). In the following graph, if you seek for a set of connected vertices from vertex s you found the set {s,3,4,7} which is the set S for the min-cut problem.

flow2

Finding a augmenting path

Find a s − t path in residual graph, it is called augmenting path. Once the path is selected, increase flow along forward edges, decrease flow along backward edges.

flow1

Publicités