Chapter 11. Network Flow

Augmenting paths in residual graphs, the max-flow / min-cut duality, and the lattice of mincuts.

This page: LLP forms. View classical forms »

Setting

A flow network is a directed graph $G = (V, E)$ with non-negative edge capacities $c(u, v)$, a designated source $s$, and a sink $t$. A flow $f$ assigns a non-negative number $f(u, v) \leq c(u, v)$ to every edge such that for each interior vertex, the inflow equals the outflow (conservation). The flow value is the net flow leaving the source. The maximum-flow problem asks for a flow of largest value.

A cut $(S, T)$ partitions the vertices with $s \in S$ and $t \in T$, and its capacity is $c(S, T) = \sum_{u \in S, v \in T} c(u, v)$. The Max-Flow Min-Cut Theorem says $\max_f |f| = \min_{(S, T)} c(S, T)$: the maximum flow value equals the minimum cut capacity. Constructive proofs hand back both objects from the same algorithm.

The FordFulkerson Algorithm

Start with the zero flow. Repeatedly find an augmenting $s \to t$ path in the residual graph $G_f$ (edges with non-zero residual capacity, including reverse edges that "undo" past flow), push the bottleneck residual capacity along that path, and update $f$. Terminate when no augmenting path remains. With integer capacities the algorithm is correct and terminates in at most $|f^*|$ iterations, each $O(|E|)$ via DFS or BFS, for a worst-case running time of $O(|E| \cdot |f^*|)$. For badly-shaped networks $|f^*|$ can be exponential in the input size.

The EdmondsKarp Algorithm

A small but pivotal refinement: always pick a shortest augmenting path (fewest edges), found via BFS in the residual graph. Distances from $s$ in $G_f$ never decrease, and after at most $O(|V| \cdot |E|)$ augmentations the algorithm halts. The total running time is $O(|V| \cdot |E|^2)$ — strongly polynomial, independent of capacity magnitudes. EdmondsKarp is the workhorse implementation: simple to implement, predictable to analyse, fast enough for most practical instances.

The Integrality Theorem and combinatorial consequences

If every capacity is an integer, then FordFulkerson (and EdmondsKarp) produces an integer-valued maximum flow. This single observation reduces several classical problems to a max-flow call on a unit-capacity graph:

• Bipartite matching. Build $L \to R$ flow with $s$ feeding every left vertex and every right vertex feeding $t$, all unit-capacity. The max flow is the maximum matching size — see Chapter 12 for the LLP-friendly direct algorithm.
• Edge-disjoint $s$-$t$ paths. Capacity-1 on every edge; the max flow equals the number of edge-disjoint paths, equal to the size of the minimum $s$-$t$ edge cut (Menger's theorem).
• Vertex-disjoint paths. Vertex-splitting trick (in/out copies with a unit edge between them) reduces this to the edge case.

The LLP perspective

The set of minimum $s$-$t$ cuts forms a finite distributive lattice under union/intersection (a consequence of cut-function submodularity). The membership predicate "$S$ is a minimum cut" is itself lattice-linear, so the LLP framework applies: searching for the least mincut $S$ that satisfies a side predicate $B$ becomes the standard LLP fixed-point problem.

For arbitrary $B$ this is NP-complete. For lattice-linear $B$, however, LLP-MinCut alternates a "fix forbidden indices under $B$" pass with a "jump to the next least mincut $\geq$ current" call, terminating in $O(MF(n, m) + km)$ time, where $MF(n, m)$ is the cost of one max-flow and $k$ counts the transitions of $B$ along any chain of cuts. Predicates that are 1-Transition (e.g., "$S$ contains both $u$ and $v$, or neither") fall in this regime.

LLP-MinCut

Driver for finding the least mincut satisfying a lattice-linear side predicate $B$. The aux methods Bcheck, forbiddenForB, and nextMincut are stubs to be specialised per predicate / per network: the first tests $B(S)$, the second flags an index that must be added to $S$ to make $B$ true, and the third jumps to the least mincut $\geq S$ via a max-flow call.

Time complexity: $O(MF(n, m) + k m)$ where $MF(n,m)$ is the cost of one max-flow and $k$ is the side-predicate transition count.

boolean[] LLPMincut(boolean[] G) {
  int n = G.length;
  boolean done = false;
  while (!done) {
    // Inner: drive every j-forbidden under B to true.
    boolean changed = true;
    while (changed) {
      changed = false;
      int j = 0;
      while (j < n) {
        if (forbiddenForB(j, G)) {
          if (G[j]) {
            return null;
          };
          G[j] = true;
          changed = true;
        };
        j = j + 1;
      }
    };
    // Now G is closed under B; jump to the least mincut >= G.
    if (Bcheck(G)) {
      done = true;
    } else {
      boolean[] next = nextMincut(G);
      if (next == null) {
        return null;
      };
      G = next;
    }
  };
  return G;
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.