maximum-flow

Maximum Flow

Overview

Use this skill to decide whether a problem is really a flow model, a cut certificate, an augmenting-path algorithm question, or a matching reduction before naming an algorithm.

Core principle: a maximum-flow answer is correct only when the model preserves capacity constraints, conservation, residual cancellation, and the cut certificate that proves optimality.

Shared CLRS Conventions

• Follow the parent clrs skill for mathematical formatting: every formula, inequality, asymptotic bound, and symbolic expression belongs in a display LaTeX block.
• Use chapter-specific theorem names here, and keep shared graph traversal mechanics in elementary-graph-algorithms.
• State the graph direction, source and sink convention, capacity domain, and whether integrality matters before using Ford-Fulkerson, Edmonds-Karp, or a matching reduction.
• Keep tables verbal. Put capacities, residual definitions, and running times in display blocks near the table instead of inside table cells.

When to Use

Use this skill when a task involves:

• modeling transport, assignment, disjoint paths, escape routes, image segmentation-style cuts, or feasibility through capacities;
• proving a flow is maximum or extracting a minimum cut from a residual network;
• choosing or analyzing Ford-Fulkerson, Edmonds-Karp, capacity scaling, or push-relabel-style production alternatives;
• reducing bipartite matching, vertex capacities, multiple sources, multiple sinks, or antiparallel directed edges to ordinary single-source single-sink flow;
• reviewing an implementation that maintains residual edges, reverse edges, bottlenecks, or integer-flow assumptions.

Do not use this skill merely because a graph is directed. If the task is shortest paths, reachability, strongly connected components, spanning trees, or topological order without capacities and conservation, route to elementary-graph-algorithms, shortest-paths, or minimun-spanning-trees as appropriate instead.