Skip to main content

Maximum Flow — MPM Algorithm

MPM (Malhotra, Pramodh-Kumar, Maheshwari) computes a maximum s–t flow in O(V³). It is close to Dinic: both work in phases on a layered residual network and find a blocking flow each phase. MPM’s novelty is how that blocking flow is built — via node potentials and a reference node, not DFS / current-edge scans alone.

This lesson follows CP-Algorithms — MPM.

Phases (like Dinic)​

  1. BFS on the residual graph → levels level[v].
  2. Keep only residual arcs with level[u] = level[v] + 1 (and that can still reach t) → layered DAG L.
  3. Find a blocking flow in L (MPM’s method below).
  4. Repeat until t is unreachable.

Fewer than V phases (same reasoning as Dinic’s level increase), so if each phase is O(V²), total is O(V³).

Potentials and the reference node​

In the current layered network L:

p_in(v)  = Σ residual capacity of arcs into v
p_out(v) = Σ residual capacity of arcs out of v
p_in(s) = p_out(t) = ∞
p(v) = min(p_in(v), p_out(v))

A reference node r minimizes p(v) among alive nodes.

Claim: you can send exactly p(r) extra flow from s to t through r, after which p(r) = 0.

Why it works: L is acyclic. Pushing p(r) out of r toward t never exceeds any later node’s p_out; pulling p(r) into r from s never exceeds earlier p_in. Simulate both pushes with BFS-style excess propagation.

Then:

  • Delete fully saturated arcs in L.
  • Delete nodes (≠ s,t) that lost all in- or out-arcs, or whose potential hit 0.

Repeat until no useful reference remains → blocking flow for the phase.

Complexity of one phase​

  • ≤ V iterations (each kills at least the reference node).
  • Charging: saturated edges deleted are paid once; at most O(V) “frontier” edges survive per iteration.

Total per phase O(V² + E) = O(V²) on dense graphs → O(V³) overall.

Implementation sketch​

Core API mirrors Dinic-style edge lists (forward + reverse residual):

struct MPM {
    // FlowEdge {v, u, cap, flow}; adj holds edge indices
    void add_edge(int v, int u, long long cap);
    long long flow(); // max flow s → t
};

Inside flow():

  1. bfs() fills level.
  2. Build in[v] / out[v] lists of layered residual arcs; accumulate pin / pout.
  3. Loop: pick alive v with minimal pot(v); if 0, remove_node; else push(v,s,f,false), push(v,t,f,true), then remove v.
🧪 MPM on a 4-node network (max flow = 5)

Check: MPM ideas​

Quiz

MPM max flow

1 / 4

MPM’s asymptotic time is…

Pick an answer to see if you are right.

Practice drills​

Activity: Node potential

Input: pin pout (non-negative ints; use a large number like 10**9 for ∞). Print min(pin, pout).

Further reading​

Cheat sheet​

IdeaTakeaway
GoalMax s–t flow
ShellDinic-like levels + blocking flow phases
p_in / p_outResidual in / out sums in layered DAG
p(v)min(p_in, p_out) (∞ at s in / t out)
Referenceargmin p; push p(r) via r
CleanupDrop saturated arcs & dead nodes
TimeO(V²) / phase, O(V³) total