How Minimum Cut Maximum Flow Theorem Works: Deep Dive with Code

1. Introduction and Core Concepts

The minimum cut maximum flow theorem is one of the most elegant and powerful results in graph theory and combinatorial optimization. First proven by L. R. Ford Jr. and D. R. Fulkerson in 1956, the theorem establishes a profound duality between two seemingly different problems on flow networks: finding the maximum amount of flow that can be sent from a source to a sink, and finding the minimum capacity set of edges whose removal disconnects the source from the sink. In essence, it states that the value of the maximum flow equals the capacity of the minimum cut.

To understand this theorem, we must first define a flow network. A flow network is a directed graph G = (V, E) where each edge (u, v) has a non-negative capacity c(u, v) that limits the amount of flow that can pass through it. There are two distinguished vertices: a source s where flow originates, and a sink t where flow is consumed. A flow is a function f: V x V -> R that satisfies two critical constraints: capacity constraint (f(u, v) <= c(u, v) for all edges) and flow conservation (for every vertex except s and t, the total flow entering equals the total flow leaving). The value of a flow |f| is the net flow out of the source.

A cut is a partition of the vertices into two disjoint sets S and T such that s is in S and t is in T. The capacity of a cut (S, T) is the sum of capacities of edges going from S to T: c(S, T) = sum c(u, v) for u in S, v in T. The minimum cut is the cut with the smallest capacity among all possible s-t cuts. Intuitively, you can think of the network as a system of pipes with different diameters; the maximum flow is the most water you can push from source to sink, while the minimum cut is the cheapest set of pipes to cut to completely stop the flow. The theorem proves these two values are always identical, which is why it matters so much for optimization, network design, and algorithm correctness proofs.

Why the Theorem Matters

The minimum cut maximum flow theorem matters because it provides both a certificate of optimality and a duality that can be exploited algorithmically. When you compute a maximum flow, you simultaneously get a proof that no larger flow is possible via the corresponding minimum cut. This is invaluable in operations research, where decision-makers need guarantees, not just heuristics. It transforms a continuous optimization problem (maximizing flow) into a combinatorial one (finding a cut) and vice versa.

Furthermore, the theorem is the foundation for dozens of other algorithms. Many problems that do not look like flow problems at first glance can be reduced to max-flow/min-cut, including bipartite matching, project selection, image segmentation, baseball elimination, and airline scheduling. Understanding this theorem unlocks a powerful modeling paradigm for solving complex real-world problems with polynomial-time algorithms.

• Flow Network: Directed graph with capacities, source, and sink.
• Feasible Flow: Assignment of flow values respecting capacity and conservation.
• s-t Cut: Partition (S,T) separating source and sink.
• Cut Capacity: Sum of capacities of forward edges crossing the cut.
• Max-Flow Min-Cut Duality: max |f| = min c(S,T) over all s-t cuts.

2. How It Works

The mechanism behind the minimum cut maximum flow theorem rests on three equivalent conditions that characterize a maximum flow. For any flow f in a network, the following statements are equivalent: 1) f is a maximum flow, 2) the residual graph G_f contains no augmenting path from s to t, and 3) |f| = c(S,T) for some cut (S,T). The proof that these are equivalent constructively shows how to find both the max flow and min cut simultaneously.

The central concept is the residual graph. Given a flow f, the residual capacity c_f(u, v) represents how much additional flow we can push on edge (u, v). If f(u, v) < c(u, v), we have forward residual capacity c(u, v) - f(u, v). If f(u, v) > 0, we have backward residual capacity f(u, v), representing the ability to cancel flow. The residual graph consists of all edges with positive residual capacity. An augmenting path is simply any directed path from s to t in this residual graph. If such a path exists, we can increase the flow by pushing additional flow along it.

When no augmenting path exists, the algorithm terminates. Let S be the set of vertices reachable from s in the residual graph, and T = V - S. By construction, s is in S, t is in T, and there are no edges from S to T with positive residual capacity in G_f. This means every edge from S to T in the original graph must be saturated (f(u,v) = c(u,v)) and every edge from T to S must carry zero flow. Consequently, the flow value |f| exactly equals the capacity c(S,T). Since no flow can exceed the capacity of any cut (a weak duality lemma), this flow must be maximal and this cut must be minimal.

Flow Networks and Cuts in Detail

Consider the weak duality lemma: for any feasible flow f and any s-t cut (S,T), the value |f| <= c(S,T). This is intuitive because all flow from s to t must cross the cut, and it cannot exceed the total capacity crossing forward. Formally, |f| = sum_{u in S, v in T} f(u,v) - sum_{u in T, v in S} f(u,v) <= sum_{u in S, v in T} c(u,v) = c(S,T). The max-flow min-cut theorem strengthens this inequality to equality at optimality. This lemma alone is useful for bounding: any cut gives an upper bound on max flow, and any flow gives a lower bound on min cut capacity.

Residual Graphs and Augmenting Paths

The residual graph is what makes iterative improvement possible. Without the backward edges, a greedy algorithm could get stuck after making a suboptimal choice. For example, if you push flow along a path that later prevents a better overall flow, the backward edges allow you to undo that decision. When you augment along a path that includes a backward edge (v,u), you are effectively reducing flow on (u,v). This cancel-and-reroute capability is essential for achieving global optimality from local augmentations. Algorithms like Ford-Fulkerson, Edmonds-Karp, and Dinic differ only in how they select augmenting paths, but all rely on this residual graph abstraction.

Proof Intuition

The classic proof is constructive and algorithmic. Assume f is a flow with no augmenting path. Define S as all vertices reachable from s via residual edges. This S defines a cut. As argued, all forward edges across this cut are saturated and backward edges are empty, so |f| = c(S,T). Since any flow's value is at most any cut's capacity, f must be maximum and (S,T) must be minimum. This simultaneously proves existence and gives a method to find the min cut once max flow is computed: just run a DFS/BFS in the final residual graph from s.

3. Implementation

Implementing the minimum cut maximum flow theorem typically means implementing a max-flow algorithm and then extracting the min cut from the final residual graph. The simplest is the Edmonds-Karp algorithm, which is the Ford-Fulkerson method using Breadth-First Search to find the shortest augmenting path (in terms of number of edges). This guarantees polynomial time and avoids the potential non-termination issues of DFS with irrational capacities.

Below is a clean implementation of Edmonds-Karp in Python. It maintains a residual capacity matrix and repeatedly finds augmenting paths with BFS. For each path, it computes the bottleneck capacity and augments the flow. This implementation is ideal for learning and for dense graphs represented as adjacency matrices. For sparse graphs, an adjacency list is more efficient.

from collections import deque

def edmonds_karp(capacity, source, sink):
    """
    Edmonds-Karp implementation for maximum flow.
    capacity: 2D matrix where capacity[u][v] is edge capacity
    source, sink: indices of source and sink vertices
    Returns (max_flow_value, residual_graph)
    """
    n = len(capacity)
    # Residual graph initially equals capacity
    residual = [row[:] for row in capacity]
    parent = [-1] * n
    max_flow = 0

    def bfs():
        """Find augmenting path using BFS, fill parent array."""
        visited = [False] * n
        queue = deque()
        queue.append(source)
        visited[source] = True
        parent[source] = -1

        while queue:
            u = queue.popleft()
            for v in range(n):
                # If not visited and residual capacity > 0
                if not visited[v] and residual[u][v] > 0:
                    queue.append(v)
                    parent[v] = u
                    visited[v] = True
                    if v == sink:
                        return True
        return False

    # Augment while there is a path from source to sink
    while bfs():
        # Find minimum residual capacity along the path
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, residual[u][v])
            v = u

        # Update residual capacities
        v = sink
        while v != source:
            u = parent[v]
            residual[u][v] -= path_flow
            residual[v][u] += path_flow
            v = u

        max_flow += path_flow

    return max_flow, residual

For larger networks, Dinic's algorithm is significantly faster. It builds a level graph using BFS and then finds blocking flows using DFS, which allows it to augment multiple paths at once. Dinic's algorithm runs in O(V^2 * E) in general, but O(min(V^(2/3), sqrt(E)) * E) for unit capacities and O(sqrt(V) * E) for bipartite matching, making it the default choice for competitive programming and production systems.

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u, v, cap):
        """Add forward and backward edge."""
        forward = [v, cap, None]  # to, capacity, rev index
        backward = [u, 0, forward]
        forward[2] = backward
        self.graph[u].append(forward)
        self.graph[v].append(backward)

    def bfs_level(self, s, t, level):
        """Build level graph."""
        queue = deque([s])
        level[:] = [-1] * self.n
        level[s] = 0
        while queue:
            u = queue.popleft()
            for v, cap, rev in self.graph[u]:
                if cap > 0 and level[v] < 0:
                    level[v] = level[u] + 1
                    queue.append(v)
        return level[t] != -1

    def dfs_flow(self, u, t, f, level, it):
        """Send flow in level graph using DFS."""
        if u == t:
            return f
        for i in range(it[u], len(self.graph[u])):
            it[u] = i
            v, cap, rev = self.graph[u][i]
            if cap > 0 and level[u] < level[v]:
                ret = self.dfs_flow(v, t, min(f, cap), level, it)
                if ret > 0:
                    # Update capacities
                    self.graph[u][i][1] -= ret
                    rev[1] += ret
                    return ret
        return 0

    def max_flow(self, s, t):
        flow = 0
        level = [0] * self.n
        INF = 10**18
        while self.bfs_level(s, t, level):
            it = [0] * self.n
            while True:
                f = self.dfs_flow(s, t, INF, level, it)
                if f == 0:
                    break
                flow += f
        return flow

Once maximum flow is computed, extracting the minimum cut is straightforward. Perform a graph traversal (BFS or DFS) from the source in the final residual graph, following only edges with residual capacity > 0. All vertices reachable form set S; the rest form T. The cut edges are those from S to T in the original graph that are saturated.

def find_min_cut(capacity, residual, source):
    """
    Find minimum s-t cut after max flow is computed.
    capacity: original capacity matrix
    residual: final residual matrix from max flow
    source: source vertex
    Returns (S_set, T_set, cut_edges)
    """
    n = len(capacity)
    visited = [False] * n
    stack = [source]
    visited[source] = True

    # DFS/BFS in residual graph to find reachable vertices
    while stack:
        u = stack.pop()
        for v in range(n):
            if not visited[v] and residual[u][v] > 0:
                visited[v] = True
                stack.append(v)

    S = [i for i in range(n) if visited[i]]
    T = [i for i in range(n) if not visited[i]]

    # Find cut edges: from S to T with original capacity > 0
    cut_edges = []
    cut_capacity = 0
    for u in S:
        for v in T:
            if capacity[u][v] > 0:
                cut_edges.append((u, v, capacity[u][v]))
                cut_capacity += capacity[u][v]

    return S, T, cut_edges, cut_capacity

The following complete example demonstrates how to set up a network, compute max flow, and then derive the min cut, verifying the theorem's equality. This pattern is reusable for any flow network modeling task.

# Complete example: verify max-flow min-cut theorem
def solve_flow_network():
    # Example network: 0 = source (s), 5 = sink (t)
    # Graph from CLRS textbook example
    n = 6
    capacity = [[0]*n for _ in range(n)]
    edges = [
        (0, 1, 16), (0, 2, 13),
        (1, 2, 10), (1, 3, 12),
        (2, 1, 4),  (2, 4, 14),
        (3, 2, 9),  (3, 5, 20),
        (4, 3, 7),  (4, 5, 4)
    ]
    for u, v, c in edges:
        capacity[u][v] = c

    source, sink = 0, 5
    max_flow, residual = edmonds_karp(capacity, source, sink)
    S, T, cut_edges, cut_cap = find_min_cut(capacity, residual, source)

    print(f"Maximum flow value: {max_flow}")
    print(f"Minimum cut capacity: {cut_cap}")
    print(f"S side (reachable): {S}")
    print(f"T side (non-reachable): {T}")
    print(f"Cut edges (S -> T): {cut_edges}")
    # Theorem verification: max_flow == cut_cap should be True
    assert max_flow == cut_cap, "Max-flow min-cut theorem violated!"
    print("Verified: max flow == min cut capacity")

solve_flow_network()

4. Step-by-Step Example

Let us walk through a concrete network with 6 vertices: source s = 0, intermediate nodes 1, 2, 3, 4, and sink t = 5. Capacities are: s->1 (16), s->2 (13), 1->2 (10), 1->3 (12), 2->1 (4), 2->4 (14), 3->2 (9), 3->t (20), 4->3 (7), 4->t (4). This is the classic example from CLRS and is ideal for illustrating augmenting paths and cut extraction.

Initialization: residual graph equals original capacities, max_flow = 0. Iteration 1: BFS finds shortest augmenting path s -> 1 -> 3 -> t with bottleneck min(16, 12, 20) = 12. Augment 12 units. Residual updates: s->1 becomes 4, 1->3 becomes 0, 3->t becomes 8, and reverse edges 1->s (12), 3->1 (12), t->3 (12) are added. Total flow = 12.

Iteration 2: BFS finds s -> 2 -> 4 -> t with bottleneck min(13, 14, 4) = 4. Augment 4. Flow = 16. Residual: s->2 = 9, 2->4 = 10, 4->t = 0, reverse edges added. Iteration 3: Path s -> 2 -> 4 -> 3 -> t. Bottleneck is min(9, 10, 7, 8) = 7. Augment 7. Flow = 23. This path uses the backward ability: 4->3 was forward, but after this, 3->4 reverse capacity appears. Iteration 4: Path s -> 1 -> 2 -> 4 -> 3 -> t is not valid due to capacities, but s -> 2 -> 1 -> 3 -> t is not either. The actual next augmenting path found by BFS is s -> 1 -> 2 -> 4 -> t? Let's trace correctly: After iteration 3, residual s->1=4, s->2=2 (13-4-7), 1->2=10, 2->4=3 (14-4-7), 4->3=0, 3->t=1 (20-12-7). BFS now finds s->1->2->4->3->t? That would be min(4,10,3,0,1) =0 invalid. Instead BFS finds s->2->1->3->t? s->2=2, 2->1=4, 1->3=0 invalid. The algorithm will find s->1->2->4->3 has no capacity, so next path is actually s->2->4->3->t is blocked. The final augmenting path is s->1->2->? Wait, we missed that after iteration 3, 3->t has 1 left. The last path is s->1 (4) ->3 (0) blocked. So BFS explores s->1 (4) and s->2 (2). From 1, can go to 2 (10). From 2, can go to 4 (3). From 4, no forward to t (0) and 4->3 (0). So no path? But we know max flow is 23, and we have flow 23, so algorithm terminates. Actually we need one more augmentation: s->1->2->4->3->t with 0 is not valid, so we are done. Wait max flow for this network is 23, which matches our current flow, so termination is correct.

Now extract min cut: BFS/DFS from s in final residual graph. Reachable vertices: s (0) can reach 1 (residual 4) and 2 (2). From 1 can reach 2 (10). From 2 can reach 4 (3). From 4 cannot reach 3 or t. So S = {0,1,2,4}, T = {3,5}. Cut edges from S to T are: 1->3 (12), 4->3 (7), 4->t (4). Sum = 12+7+4 = 23. This equals max flow value 23, verifying the theorem. Note that edge 2->? Actually 2 has no edge to 3, so not counted. This cut is minimal; any other s-t cut has capacity >= 23. For example, cut ({s}, {1,2,3,4,t}) has capacity 16+13=29 > 23.

Visualizing the Cut

Imagine drawing the graph and circling S on the left and T on the right. All edges crossing from left to right are saturated, meaning they are bottlenecks. If you increase capacity of any cut edge, max flow would increase. Conversely, decreasing any cut edge would decrease max flow. This visualization helps in network design: to increase throughput, you must increase capacity of the minimum cut, not just any edge.

5. Complexity Analysis

Complexity of max-flow algorithms depends heavily on how augmenting paths are chosen and the graph representation. The naive Ford-Fulkerson method using DFS can be exponential in the worst case with irrational capacities, and even with integer capacities its complexity is O(E * |f*|) where |f*| is the max flow value, which is pseudo-polynomial and can be huge if capacities are large (e.g., 10^9).

Edmonds-Karp improves this to polynomial time by always choosing the shortest augmenting path via BFS. Each augmentation takes O(E) time for BFS, and there are at most O(V * E) augmentations, giving O(V * E^2). While polynomial, this can still be slow for dense graphs with thousands of vertices. Dinic's algorithm is faster in practice and theory, achieving O(V^2 * E), which is better for most graphs, and even faster for special cases like unit capacities.

More advanced algorithms like Push-Relabel (Goldberg-Tarjan) achieve O(V^3) or O(V^2 * sqrt(E)) with heuristics, and are often the fastest in practice for dense graphs. For very large graphs, capacity scaling and other heuristics are used. Space complexity is generally O(V^2) for matrix representation or O(V + E) for adjacency list, plus O(V) for BFS queues and parent arrays.

When choosing an algorithm, consider graph density, capacity range, and implementation complexity. For interview settings and moderate graphs (V < 500), Edmonds-Karp is sufficient and easy to code. For competitive programming or production with V up to 5000 and E up to 50000, Dinic or Push-Relabel is preferred. Always use adjacency lists for sparse graphs to save memory and improve cache performance.

6. Variations and Optimizations

Several important variations extend the basic max-flow min-cut framework. The most common is the minimum cut with multiple sources and sinks, which is reduced to single source/sink by adding a super-source connected to all sources with infinite capacity and a super-sink connected from all sinks. Another variation is the global minimum cut (without designated s and t), solved by Stoer-Wagner algorithm in O(V^3) or O(V * E log V), which finds the smallest cut separating any two vertices.

Capacity scaling is a powerful optimization for Ford-Fulkerson. Instead of augmenting by any path, it augments along paths with large bottleneck first, using a scaling parameter Delta that starts at the highest power of two <= max capacity and halves each phase. This reduces the number of augmentations to O(E log U) and gives O(E^2 log U) total time, which is excellent when capacities are large but E is moderate. It also avoids the bad case where many small augmentations are needed.

For undirected graphs, each undirected edge is replaced by two directed edges with the same capacity. Node capacities (limits on flow through a vertex) are modeled by splitting each vertex v into v_in and v_out connected by an edge with capacity equal to node capacity. Lower bounds on flows (requiring at least L units on an edge) are handled by transforming to a circulation problem with demands. These reductions show the flexibility of flow modeling.

Advanced Algorithms

Dinic with scaling and Push-Relabel with gap and global relabeling heuristics are state-of-the-art. Push-Relabel maintains a preflow (allowing excess at nodes) and pushes flow downhill based on height labels, which is very cache-friendly and parallelizable. For unit networks (all capacities = 1), Dinic runs in O(min(V^(2/3), sqrt(E)) * E), which is near-linear for bipartite matching. Recent theoretical advances have achieved almost-linear time O(E^(1+o(1))) for max flow, but these are complex and not yet practical for typical implementations.

Choosing the Right Variant

If you need only the min cut value and not the flow assignment, you can use max-flow algorithms as a black box. If you need all minimum cuts (there can be exponentially many), you can build the cactus representation or the Picard-Queyranne DAG of all minimum cuts from the residual graph. For dynamic networks where capacities change slightly, dynamic max-flow algorithms can recompute faster than from scratch by reusing previous flows.

7. Real-World Applications

The minimum cut maximum flow theorem has surprisingly broad real-world applications far beyond obvious network routing. In computer vision, the graph cut technique for image segmentation models each pixel as a node, with edges to source (foreground) and sink (background) weighted by pixel likelihood, and edges between neighboring pixels weighted by similarity. The minimum s-t cut then gives the optimal segmentation that balances data fidelity and smoothness, powering tools like Photoshop's selection and medical image analysis.

In project selection and open-pit mining, each project has a profit (positive) or cost (negative) and dependencies (if you choose project A you must also choose B). This is modeled as a flow network where source edges represent profits, sink edges represent costs, and infinite capacity edges represent dependencies. The minimum cut identifies the optimal subset of projects to maximize total profit, which is the complement of the cut capacity. Similar models apply to portfolio optimization and feature selection.

In web servers, databases, and distributed systems, max flow is used for load balancing and resource allocation. For example, assigning requests to servers with capacity constraints, or sharding database queries, can be formulated as bipartite matching (a special case of max flow). Network reliability analysis uses min cut to find the most vulnerable set of links whose failure would disconnect the network, guiding infrastructure investment. Airline crew scheduling, baseball elimination (determining if a team can still finish first), and even bipartite matching for job assignments all reduce to max flow.

Even in social networks, min cut is used to find communities and to identify the minimum set of users to remove to disconnect two groups, which is useful for studying influence propagation and for network immunization strategies.

8. Comparison with Alternatives

While max-flow/min-cut is powerful, it is not always the right tool. For shortest path problems (finding minimum distance between two nodes), Dijkstra or Bellman-Ford is more appropriate than max flow, which optimizes throughput, not distance. For minimum spanning tree (connecting all nodes cheapest), Kruskal or Prim is correct, whereas min cut only separates s and t. Understanding when to use flow versus other graph algorithms is crucial for efficient problem solving.

Compared to linear programming, max flow is a special case that can be solved much faster with combinatorial algorithms. General LP would be overkill and slower. Compared to brute force enumeration of all cuts (which is exponential, 2^(V-2) possible s-t cuts), max-flow algorithms are exponentially faster. Compared to heuristic approaches like greedy augmentation without residual graphs, max-flow algorithms guarantee optimality, while greedy can get stuck at suboptimal solutions.

Within max-flow algorithms themselves, the trade-offs are implementation complexity versus performance. Edmonds-Karp is simplest to implement correctly, Dinic is moderately complex but much faster, and Push-Relabel is fastest for dense graphs but trickier to code bug-free. For many interview and practical purposes, Dinic offers the best balance.

In summary, if your problem can be modeled as flow with capacities and you need throughput or cut capacity, use max-flow. If you need shortest distance, use Dijkstra. If you need to connect all nodes, use MST algorithms. The key skill is recognizing the reduction: many problems that ask for maximum assignment, minimum removal to disconnect, or optimal selection with constraints are secretly flow problems.

9. Common Mistakes and Best Practices

One of the most common mistakes is forgetting to add reverse edges in the residual graph. Beginners often implement Ford-Fulkerson by only reducing forward capacity, without increasing reverse capacity. This prevents the algorithm from undoing bad augmentations and leads to suboptimal flows that are not maximal. Always update both directions: residual[u][v] -= path_flow and residual[v][u] += path_flow, even if the reverse edge did not exist originally (initialize it to 0).

Another frequent pitfall is using DFS instead of BFS for Edmonds-Karp and assuming it is still polynomial. DFS can cause the algorithm to take exponentially many augmentations if capacities are large, or even fail to terminate with irrational capacities. For correctness and performance guarantees, use BFS to find the shortest augmenting path. Also, be careful with integer overflow and floating point capacities: use Python's large integers or handle floats with epsilon comparisons, and be aware that max flow value can exceed 32-bit range.

A subtle bug is misidentifying the min cut after max flow. The cut is defined by vertices reachable from source in the final residual graph, not by saturated edges alone. Some saturated edges may not be in the minimum cut if they are not crossing from S to T. To extract the cut correctly, run BFS/DFS from source using only edges with residual > 0, then collect edges from S to T in the original graph. Also, remember that the min cut may not be unique; your algorithm will find one of them.

Best Practices

Use adjacency lists with edge objects (to, rev, cap) for sparse graphs to achieve O(V+E) memory and faster traversals. For dense graphs, matrix is acceptable but slower. Always validate inputs: capacities should be non-negative, graph should be connected enough to have a path. Add a super-source and super-sink for multiple sources/sinks to simplify code. Test with known examples (like the CLRS graph) and verify that max flow equals min cut capacity as a sanity check.

For production code, consider using iterative BFS/DFS to avoid recursion depth limits, and use deque for efficient queues. Profile your implementation: if V > 1000, prefer Dinic over Edmonds-Karp. Document whether your graph is directed or undirected (for undirected, add two directed edges). Finally, when modeling real problems, ensure you correctly set infinite capacities: use a value larger than sum of all finite capacities (e.g., 10**18) rather than float('inf') to avoid arithmetic issues.

• Always maintain residual graph with forward and backward edges.
• Use BFS for Edmonds-Karp to guarantee polynomial time.
• Extract min cut via reachability in final residual graph, not just saturated edges.
• Choose adjacency list for sparse graphs, matrix only for dense or small graphs.
• Verify max_flow == min_cut_capacity as an invariant check.
• Handle multiple sources/sinks with super-source/super-sink reduction.

10. Interview Questions

Interview questions about the minimum cut maximum flow theorem test both theoretical understanding and coding ability. Interviewers often ask you to model a novel problem as a flow network, implement a max-flow algorithm, or reason about cuts. Below are common questions with guidance on how to approach them.

Q1: Explain the Max-Flow Min-Cut Theorem and Prove Weak Duality

Expected answer: State the theorem (max |f| = min c(S,T)), define flow, cut, capacity, then prove that for any flow f and any cut (S,T), |f| <= c(S,T). Show that flow across cut equals sum of flows on forward edges minus backward edges, which is <= sum of capacities. Then explain why equality at termination implies optimality. Be ready to draw a small example and show a cut. This tests conceptual depth, not just memorization.

Q2: Implement Edmonds-Karp or Dinic to Compute Max Flow

You will be given n, edge list, source, sink, and asked to return max flow. Focus on correct BFS, residual updates, and bottleneck calculation. Handle 0-indexed vs 1-indexed inputs. Discuss complexity O(V*E^2) for Edmonds-Karp and why BFS matters. Bonus: also return the min cut edges. Practice coding this without bugs under time pressure, and remember to escape comparisons correctly and handle large graphs efficiently.

Q3: How Would You Find the Minimum Cut After Computing Max Flow?

Answer: After max flow, run BFS/DFS from source in residual graph following edges with residual > 0. All visited nodes are S, rest are T. Cut edges are original edges from S to T. Cut capacity is sum of their capacities, which equals max flow. Mention that this is O(V+E) and gives a certificate. Be prepared to code find_min_cut function as shown in Section 3. Interviewers may ask to enumerate all min cuts or find the minimum s-t cut with minimum number of edges among all min cuts (use secondary BFS).

Q4: Reduce Bipartite Matching to Max Flow

This is a classic reduction question. Given bipartite graph (L,R,E), create source connected to all L with capacity 1, all R connected to sink with capacity 1, and edges L->R with capacity 1 (or infinite). Max flow equals maximum matching size, and min cut corresponds to minimum vertex cover (Kőnig's theorem). Explain construction, prove correctness, and state that Dinic runs in O(sqrt(V)*E) for this case, which is efficient. This tests modeling skill.

Q5: What Happens If Capacities Are Irrational or Floating Point?

Discuss that Ford-Fulkerson with DFS may not terminate or may converge to a value not equal to max flow with irrational capacities (Zwick's example). Edmonds-Karp and other polynomial algorithms still work if capacities are rational (scale to integers) but with floats you need epsilon handling and may have precision issues. In practice, scale to integers or use capacity scaling. Mention that the theorem still holds mathematically for real capacities, but algorithmic guarantees require care. This tests awareness of edge cases and numerical stability.

To excel in interviews, practice modeling at least five reductions (bipartite matching, project selection, baseball elimination, image segmentation, circulation with demands), be able to code Dinic from memory, and be ready to analyze complexity and prove correctness on the whiteboard. Understanding the duality deeply will help you answer follow-ups confidently.