MPM Algorithm

Purpose: Malhotra-Pramodh Kumar-Maheshwari (1978) — compute a blocking flow in $O(n^2)$ instead of Dinic’s $O(nm)$, giving an $O(n^3)$ maximum flow algorithm. The best choice for dense graphs.

The Idea: potentials

Inside a level graph, define for each vertex

$p(v)=\min (\underset{\text{inflow capacity}}{\underbrace{{\sum }_{\text{in}}{c}_f}},\underset{\text{outflow capacity}}{\underbrace{{\sum }_{\text{out}}{c}_f}}),$

with $p(s)$ and $p(t)$ counting only outgoing and incoming capacity respectively.

The vertex with minimum potential $v^{\ast }$ can have all of $p(v^{\ast })$ pushed through it immediately: push $p(v^{\ast })$ forward to $t$ greedily, and pull $p(v^{\ast })$ backward from $s$ greedily. Because $v^{\ast }$ has the smallest potential, no vertex downstream or upstream can block the push — every one of them can absorb at least that much.

After the push, $v^{\ast }$ is saturated and gets deleted, along with any vertex whose potential drops to zero.

Algorithm

BlockingFlow(level graph L):
    compute p(v) for all v
    while s and t are still present:
        v* = argmin p(v)
        if p(v*) == 0: delete v*, update potentials; continue
        push p(v*) forward from v* to t   (greedy, saturating edges in order)
        pull p(v*) backward from v* to s
        update potentials of affected vertices
        delete v* and any vertex with p = 0

Complexity

Per blocking flow:

• Each vertex is deleted once: $O(n)$ deletions.
• Each push/pull either saturates an edge (at most $m$ times total) or exhausts $p(v^{\ast })$ (at most once per vertex per phase, $O(n)$ per deletion).
• Potential updates cost $O(n)$ per deleted vertex with an adjacency matrix.

$\text{Blocking flow: }O(n^2),\text{Max flow: }O(n)\text{ phases}\times O(n^2)=O(n^3).$

When MPM beats Dinic

Graph	Dinic	MPM
Sparse, $m=O(n)$	$O(n^{2}m)=O(n^3)$	$O(n^3)$ — tie
Dense, $m=\Theta (n^2)$	$O(n^{2}m)=O(n^4)$	$O(n^3)$ — MPM wins
Unit capacities	$O(m\sqrt{n})$ — Dinic wins	$O(n^3)$
Bipartite matching	$O(m\sqrt{n})$ — Dinic wins	$O(n^3)$

So MPM is the right tool exactly when the graph is dense and capacities are large — the same regime where push-relabel with the highest-label rule also shines, and push-relabel is usually faster in practice.

Reality check

Dinic’s $O(n^{2}m)$ bound is famously pessimistic; on real inputs it behaves far better. Unless a problem is specifically constructed to defeat it (dense graph, adversarial capacities), write Dinic. MPM’s value is the $O(n^3)$ guarantee.

Variants / Use Cases

• Dinic — the blocking-flow framework MPM slots into
• Maximum Flow — the topic page
• Karzanov — the earlier $O(n^3)$ preflow algorithm with a similar goal
• Push-relabel — the modern $O(n^3)$ choice, generally faster in practice