Max Flow

In this applet we realize Ford and Fulkerson's Max Flow algorithm.

The Max Flow problem consist of a directed graph, edges are labeled with capacities, and there are two distinct nodes: the source (pink) and the sink (orange). A flow is an assignment of flows to each each, such that

the flow does not exceed the capacity for each edge,
the sum of the incoming flows equals the sum of the outgoing flows for each edge, but the source or the sink.

The aim is to find a flow which maximizes the incoming flow at the sink.

Ford and Fulkerson's algorithm

Ford and Fulkerson's algorithm is very old, but very simple. It starts with the null-flow and repeats the following stage until the Max Flow is reached: In the stage the algorithm tries to find a path from the source to the sink, such that the flow in the corresponding edges, can be augmented. This is called an augmenting path. (Drawn in red in the applet below).

The button run executes once this stage.

This applet is made by Ninh Lê Ðúc and Christoph Dürr.

Open problem

Here is an open problem for Max Flow fans.

Let G be a bipartite graph, where the left nodes are sources and the right nodes are sinks. We have two commodities (kind of flows), say red and blue. Every source has an associated red and blue offer and every sink has an associated red and blue demand. Every edge can transport exactly one red, one blue flow or no flow at all. We say that the edge has integer capacity 1. We want to know if there is a flow satisfying all offers and demands, not exceeding edge capacities. This problem is called the 2-LAYERS 2-COMMODITY INTEGER FLOW problem.

It is NP-hard if G is an arbitrary bipartite graph. What is its complexity for the complete bipartite graph?