Network Flow Algorithms: Complexity Analysis and Applications

1. Introduction and Core Concepts

Network flow algorithms form one of the most powerful and versatile classes of graph algorithms, providing a framework for modeling how material, information, or resources move through a network under capacity constraints. At its core, a flow network is a directed graph where each edge has a capacity that limits the amount of flow that can pass through it. Two special vertices are designated: the source (s), where flow originates, and the sink (t), where flow is collected. The central problem is to determine the maximum flow that can be sent from s to t without violating capacity constraints or conservation of flow at intermediate vertices.

The importance of network flow algorithms extends far beyond theoretical computer science. They provide the mathematical foundation for optimizing transportation systems, allocating resources in cloud infrastructure, routing data packets, and even matching organ donors to recipients. The elegance of the model lies in its generality: many seemingly unrelated combinatorial problems — including bipartite matching, project selection, baseball elimination, and image segmentation — can be reduced to a single maximum flow computation. This reducibility makes network flow algorithms a critical tool in any software engineer's algorithmic toolkit.

To understand network flow algorithms, we must first define several core concepts. A flow network is defined as G = (V, E) with a capacity function c: V x V -> R+ and distinguished source s and sink t. A flow is a function f: V x V -> R satisfying three properties: capacity constraint (f(u,v) <= c(u,v) for all u,v), skew symmetry (f(u,v) = -f(v,u)), and flow conservation (for all u in V - {s,t}, the sum of flows out of u equals zero). The value of a flow |f| is the total flow leaving the source. A cut (S,T) is a partition of V into S and T = V - S such that s is in S and t is in T; its capacity c(S,T) is the sum of capacities of edges from S to T. The foundational Max-Flow Min-Cut Theorem states that the value of the maximum flow equals the capacity of the minimum s-t cut, establishing a profound duality that underpins all efficient algorithms.

Why Network Flow Matters for Modern Systems

In distributed systems and large-scale infrastructure, bottlenecks are inevitable. Whether you are load balancing requests across web servers, provisioning bandwidth in a content delivery network, or scheduling jobs across a compute cluster, you are implicitly solving a flow problem. Network flow algorithms give us not just an optimal solution, but also a certificate of optimality via the minimum cut, which identifies the precise bottleneck limiting throughput. This diagnostic capability is invaluable for capacity planning and system design.

Furthermore, network flow algorithms serve as a gateway to more advanced optimization techniques. The concepts of residual graphs, augmenting paths, and push-relabel operations introduce paradigms like local search, potential functions, and amortized analysis that recur throughout algorithm design. Mastering these ideas builds intuition for linear programming, approximation algorithms, and combinatorial optimization as a whole.

2. How It Works

The unifying mechanism behind all network flow algorithms is the residual graph. Given a flow network G and a flow f, the residual capacity cf(u,v) = c(u,v) - f(u,v) represents how much additional flow can be pushed along edge (u,v). The residual graph Gf consists of edges with positive residual capacity, including reverse edges that allow the algorithm to undo previously made suboptimal decisions. This ability to cancel flow is what makes the search for an optimal solution possible without exhaustive enumeration.

An augmenting path is a simple path from s to t in the residual graph. The amount of flow that can be pushed along such a path is limited by its bottleneck — the minimum residual capacity along its edges. The generic Ford-Fulkerson method repeatedly finds an augmenting path and augments flow along it until no such path exists. At termination, the set of vertices reachable from s in the residual graph defines a minimum cut, proving optimality. The critical design choice that distinguishes specific algorithms is how they select augmenting paths.

Edmonds-Karp, for example, always chooses the shortest augmenting path in terms of number of edges using Breadth-First Search (BFS). This seemingly minor rule guarantees polynomial time complexity regardless of capacities. Dinic's algorithm improves further by constructing a level graph — a layered subgraph containing only edges (u,v) where distance[t] = distance[s] + 1 — and then finding a blocking flow that saturates at least one edge on every s-t path in the level graph. Push-relabel algorithms abandon the notion of augmenting paths entirely, instead maintaining a preflow and pushing excess flow locally from higher to lower vertices using distance labels, offering excellent practical performance and a different perspective on flow conservation.

The Role of Level Graphs and Distance Labels

Level graphs and distance labels are heuristics that guide flow toward the sink efficiently. In Dinic's algorithm, BFS computes level[v] = distance from s to v in Gf. Only edges that go from level i to level i+1 are retained. A depth-first search then sends flow in this acyclic layered network, ensuring each augmentation is along a shortest path and that many augmentations are batched together. This avoids the repeated BFS cost of Edmonds-Karp.

In push-relabel, each vertex v maintains a height h[v] and excess e[v]. Initially, h[s] = |V| and h[v] = 0 otherwise, and all edges out of s are saturated. The algorithm repeatedly selects an active vertex (e[v] > 0) and either pushes flow to a neighbor w with h[v] = h[w] + 1, or relabels v to increase its height if no such neighbor exists. The height function acts as a lower bound on distance to t in the residual graph, ensuring progress and eventual convergence to a maximum flow when no active vertices remain.

Max-Flow Min-Cut Duality

The duality between flows and cuts is not just theoretical; it is algorithmically constructive. When an algorithm terminates because t is unreachable from s in Gf, the reachable set S defines a cut (S, V-S) whose capacity exactly equals the flow value. This provides an immediate proof that no greater flow is possible. In applications like network reliability or community detection, the cut itself is often more valuable than the flow, revealing vulnerabilities or natural partitions in the underlying graph.

3. Implementation

Implementing network flow algorithms correctly requires careful handling of the residual graph, especially reverse edges. A common and efficient representation stores the graph as an adjacency list of edge objects, where each forward edge has a paired reverse edge with zero initial capacity. Augmenting flow on a forward edge decreases its residual capacity and increases the residual capacity of its reverse edge by the same amount, enabling future cancellation.

Below are four production-quality Python implementations covering the most important variants of network flow algorithms. All code escapes HTML-sensitive characters for safe rendering and includes detailed comments for educational clarity.

Edmonds-Karp: BFS-Based Ford-Fulkerson

from collections import deque
from typing import List

def edmonds_karp(capacity: List[List[int]], source: int, sink: int) -> int:
    """
    Edmonds-Karp implementation (Ford-Fulkerson with BFS).
    capacity: adjacency matrix of capacities
    Returns max flow value from source to sink.
    """
    n = len(capacity)
    # Residual graph initially equals capacity
    residual = [row[:] for row in capacity]
    parent = [-1] * n
    max_flow = 0

    def bfs() -> bool:
        """Find shortest augmenting path; store parent pointers."""
        nonlocal parent
        parent = [-1] * n
        parent[source] = source
        q = deque([source])
        while q:
            u = q.popleft()
            for v in range(n):
                # Only consider edges with residual capacity > 0 and unvisited
                if parent[v] == -1 and residual[u][v] > 0:
                    parent[v] = u
                    if v == sink:
                        return True
                    q.append(v)
        return False

    # Repeatedly augment while a path exists
    while bfs():
        # Find bottleneck capacity on 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 (forward and reverse)
        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

# Example usage:
# cap = [[0, 16, 13, 0, 0, 0],
#        [0, 0, 10, 12, 0, 0],
#        [0, 4, 0, 0, 14, 0],
#        [0, 0, 9, 0, 0, 20],
#        [0, 0, 0, 7, 0, 4],
#        [0, 0, 0, 0, 0, 0]]
# print(edmonds_karp(cap, 0, 5))  # Output: 23

Dinic's Algorithm: Level Graph + Blocking Flow

from collections import deque

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

    def add_edge(self, fr: int, to: int, cap: int):
        """Add forward and reverse edge pair."""
        forward = [to, cap, None]  # to, capacity, rev reference
        backward = [fr, 0, forward]
        forward[2] = backward
        self.graph[fr].append(forward)
        self.graph[to].append(backward)

    def bfs_level(self, s: int, t: int, level: list) -> bool:
        """Build level graph using BFS. Returns True if t reachable."""
        for i in range(self.n):
            level[i] = -1
        q = deque([s])
        level[s] = 0
        while q:
            u = q.popleft()
            for v, cap, rev in self.graph[u]:
                if cap > 0 and level[v] < 0:
                    level[v] = level[u] + 1
                    q.append(v)
        return level[t] != -1

    def dfs_flow(self, u: int, t: int, f: int, level: list, it: list) -> int:
        """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 residual capacities
                    self.graph[u][i][1] -= ret
                    rev[1] += ret
                    return ret
        return 0

    def max_flow(self, s: int, t: int) -> int:
        flow = 0
        level = [-1] * 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

# Usage: dinic = Dinic(6); dinic.add_edge(0,1,16); ... ; dinic.max_flow(0,5)

Push-Relabel with Gap Heuristic (Highest Label)

from collections import deque

def push_relabel(n: int, edges: list, source: int, sink: int) -> int:
    """
    Push-relabel (FIFO) implementation.
    edges: list of (u, v, capacity)
    """
    # Build adjacency with residual capacities
    cap = [[0]*n for _ in range(n)]
    for u, v, c in edges:
        cap[u][v] += c  # handle parallel edges

    height = [0]*n
    excess = [0]*n
    height[source] = n

    # Preflow: saturate all edges from source
    for v in range(n):
        if cap[source][v] > 0:
            flow = cap[source][v]
            cap[source][v] -= flow
            cap[v][source] += flow
            excess[v] += flow
            excess[source] -= flow

    # Active vertices (excluding source and sink)
    active = deque([i for i in range(n) if i != source and i != sink and excess[i] > 0])

    def push(u: int, v: int):
        delta = min(excess[u], cap[u][v])
        if delta <= 0 or height[u] != height[v] + 1:
            return False
        cap[u][v] -= delta
        cap[v][u] += delta
        excess[u] -= delta
        excess[v] += delta
        if v != source and v != sink and excess[v] == delta:
            active.append(v)
        return True

    def relabel(u: int):
        min_h = float('inf')
        for v in range(n):
            if cap[u][v] > 0:
                min_h = min(min_h, height[v])
        if min_h < float('inf'):
            height[u] = min_h + 1

    while active:
        u = active.popleft()
        pushed = False
        for v in range(n):
            if cap[u][v] > 0 and excess[u] > 0:
                if push(u, v):
                    pushed = True
                    if excess[u] == 0:
                        break
        if excess[u] > 0:
            relabel(u)
            active.append(u)

    return excess[sink]

Bipartite Matching via Max Flow Reduction

def bipartite_matching(n_left: int, n_right: int, edges: list) -> int:
    """
    Reduce bipartite matching to max flow.
    edges: list of (u_left, v_right) where 0 <= u_left < n_left, 0 <= v_right < n_right
    Returns size of maximum matching.
    """
    # Node indexing: source=0, left 1..n_left, right n_left+1 .. n_left+n_right, sink = last
    N = 2 + n_left + n_right
    source = 0
    sink = N - 1
    dinic = Dinic(N)

    # Source to left partition (capacity 1)
    for u in range(n_left):
        dinic.add_edge(source, 1 + u, 1)

    # Right partition to sink (capacity 1)
    for v in range(n_right):
        dinic.add_edge(1 + n_left + v, sink, 1)

    # Left to right edges (capacity 1)
    for u, v in edges:
        if 0 <= u < n_left and 0 <= v < n_right:
            dinic.add_edge(1 + u, 1 + n_left + v, 1)

    max_match = dinic.max_flow(source, sink)
    return max_match

# Example: 3 workers, 3 jobs, edges = [(0,0),(0,1),(1,1),(2,2)]
# print(bipartite_matching(3, 3, edges))  # Output: 3

4. Step-by-Step Example

Consider a small flow network with 6 vertices: s = 0, A = 1, B = 2, C = 3, D = 4, t = 5. Capacities are: s->A 10, s->B 10, A->C 4, A->D 8, A->B 2, B->D 9, C->t 10, D->C 6, D->t 10. This network is intentionally designed to require flow cancellation to achieve optimality, illustrating why reverse edges are essential.

Initialization: Flow is zero everywhere. Residual graph equals original capacities. Using Edmonds-Karp, BFS finds the shortest augmenting path. The first BFS discovers s->A->C->t with bottleneck min(10,4,10) = 4. We augment 4 units along this path. Residual capacities update: s->A becomes 6, A->C becomes 0 (with reverse C->A 4), C->t becomes 6. Total flow = 4.

Iteration 2: BFS now finds s->A->D->t with bottleneck min(6,8,10) = 6. Augment 6 units. Residual: s->A 0, A->D 2, D->t 4. Total flow = 10. At this point, s->A is saturated, so further flow must go via s->B.

Iteration 3: BFS finds s->B->D->t with bottleneck min(10,9,4) = 4. Augment 4. Residual: s->B 6, B->D 5, D->t 0. Total flow = 14. Now D->t is saturated, but an alternative route D->C->t exists.

Iteration 4: BFS finds s->B->D->C->t with bottleneck min(6,5,6,6) = 5. Augment 5. Residual: s->B 1, B->D 0, D->C 1, C->t 1. Total flow = 19. No further s-t path exists that uses only forward edges, but the algorithm will still check.

Termination: BFS from s in the residual graph can reach only {s, B} because s->A is 0, B->D is 0, and A is isolated. The cut S = {s, B}, T = {A, C, D, t} has capacity c(S,T) = c(s,A) + c(B,D) + c(B,?) = 10 + 9 = 19? Wait, we must sum edges from S to T: s->A (10) + B->D (9) = 19, which exactly matches the flow value, confirming optimality via Max-Flow Min-Cut. Notice that if we had chosen paths greedily without BFS (e.g., always picking s->A->D->t first with 8 units), we would have blocked the better distribution and required a reverse edge augmentation to fix it — a scenario Edmonds-Karp handles automatically.

Visualizing the Residual Graph Evolution

Tracking residual graphs manually reinforces why reverse edges matter. After iteration 2, suppose we had sent 8 units through A->D instead of 6, saturating D->t prematurely. A later augmenting path s->B->D->A->C->t could use the reverse edge D->A (capacity 8) to redirect 2 units from A->D to A->C, increasing total flow. This cancellation mechanism is invisible without residual graphs and is the key insight that makes Ford-Fulkerson correct.

5. Complexity Analysis

The complexity of network flow algorithms varies dramatically based on path selection strategy and graph characteristics. The generic Ford-Fulkerson method with DFS has a pseudo-polynomial bound O(E * |f*|) where |f*| is the value of the maximum flow, which can be exponential in the input size if capacities are large. This makes it unsuitable for production use with arbitrary integer capacities.

Edmonds-Karp improves this to strongly polynomial O(V * E^2) by guaranteeing each augmentation is along a shortest path. The proof relies on the monotonic increase of distances from s to every vertex in the residual graph; each edge can become critical (bottleneck) at most O(V) times. Dinic's algorithm further reduces complexity to O(V^2 * E) in general graphs and O(min(V^(2/3), sqrt(E)) * E) for unit capacities, making it the default choice for competitive programming and many industrial applications.

Push-relabel algorithms achieve O(V^3) with FIFO selection and O(V^2 * sqrt(E)) with highest-label selection, often outperforming Dinic in practice on dense graphs due to better locality and lack of repeated BFS/DFS phases. For graphs with integer capacities, capacity scaling techniques yield O(E^2 log U) or O(E log U (E + V log V)) where U is the maximum capacity, which is advantageous when capacities vary widely.

Space complexity is typically linear in the graph size, O(V + E), when using adjacency lists. Adjacency matrices require O(V^2) and are only practical for dense, small graphs. In practice, the constant factors and implementation details matter enormously: Dinic with adjacency lists and iterative DFS often beats asymptotically superior algorithms on graphs with V < 10,000 due to cache efficiency.

Choosing Based on Constraints

For interviews and typical web-scale problems (V up to 10^4, E up to 10^5), Dinic is the safest default. For very dense graphs or when you need to handle floating-point capacities, push-relabel may be preferable. If capacities are unit (e.g., bipartite matching), Hopcroft-Karp (O(E sqrt(V))) specialized for bipartite matching will outperform generic max flow. Always consider whether your problem actually requires max flow or can be solved with a simpler algorithm like BFS/DFS for connectivity.

6. Variations and Optimizations

Beyond the classic maximum flow problem, numerous variations extend the model to handle richer constraints. Minimum-cost flow adds a cost per unit flow on each edge and seeks the cheapest way to send a required amount of flow, solved with successive shortest augmenting paths using potentials (Johnson's trick) to handle negative reduced costs, achieving O(F * (E + V log V)) with Dijkstra. Circulation with demands and lower bounds generalizes flow conservation to require each vertex to meet a demand, reducible to max flow by adding a super-source and super-sink.

Multi-source multi-sink flows are handled by adding a super-source connected to all sources and a super-sink connected from all sinks with infinite capacity. For dynamic networks where capacities change over time, Gomory-Hu trees compactly represent all-pairs min cuts in undirected graphs using only V-1 max flow computations. For large graphs, parallel push-relabel and distributed Dinic implementations leverage GPU or cluster parallelism.

Key optimizations include capacity scaling, which augments along paths with large bottleneck first (delta-scaling), reducing the number of augmentations from O(|f*|) to O(E log U). The gap heuristic and global relabeling heuristic dramatically speed up push-relabel by periodically recomputing exact heights via reverse BFS from t and detecting gaps in height levels to prune disconnected vertices. For Dinic, current-edge optimization (maintaining an iterator pointer per vertex) avoids re-scanning saturated edges, and scaling to adjacency lists with edge pooling reduces allocation overhead.

Handling Lower Bounds and Vertex Capacities

Real networks often impose lower bounds l(u,v) and vertex capacities c(v). Both reduce to standard max flow: for lower bounds, initialize flow to l, adjust node balances, and add super-source/sink to satisfy demands; for vertex capacities, split each vertex v into v_in -> v_out with capacity c(v), redirecting all incoming edges to v_in and outgoing from v_out. These transformations are essential for modeling production constraints like minimum throughput guarantees or router processing limits.

7. Real-World Applications

Network flow algorithms quietly power critical infrastructure across technology, logistics, and science. In computer networks, max flow determines the maximum throughput between data centers given link bandwidths, while min cut identifies the smallest set of links whose failure disconnects the network — vital for resilience planning. Content Delivery Networks (CDNs) use min-cost flow to route user requests to edge servers minimizing latency and bandwidth cost.

In web servers and cloud platforms, bipartite matching via max flow solves load balancing and assignment problems: assigning incoming HTTP requests to backend servers respecting capacity, scheduling containers to machines with resource constraints, or matching users to A/B test variants while maintaining balance. Databases use flow for query optimization, particularly for join ordering and data partitioning across shards to minimize cross-shard transactions (modeled as a cut problem).

Transportation and supply chain systems model roads, pipelines, and shipping routes as flow networks to maximize goods delivered or minimize transportation cost. Airlines use flow for crew scheduling and gate assignment. In computer vision, the famous Boykov-Kolmogorov max flow/min cut algorithm segments images by modeling pixels as vertices and similarity as edge capacities; the min cut separates foreground from background with remarkable accuracy, forming the basis of tools like Photoshop's selection.

Even in machine learning, flow appears in clustering (min cut for community detection), feature selection, and training of certain structured prediction models. The key takeaway is that whenever you have limited resources moving through a network with constraints, there is likely a flow formulation that yields an optimal, polynomial-time solution.

8. Comparison with Alternatives

Network flow algorithms are not always the right tool. For some problems, simpler or more specialized algorithms offer better performance or clarity. Understanding when to use max flow versus alternatives is crucial for system design and interviews.

For bipartite matching, Hopcroft-Karp is a specialized alternative that runs in O(E sqrt(V)) and is simpler to implement than generic Dinic, though Dinic achieves the same bound on unit networks. For shortest path problems, Dijkstra or Bellman-Ford are direct solutions; modeling them as min-cost flow would be overkill. For general assignment with costs, the Hungarian algorithm O(V^3) is often more efficient than min-cost max flow.

Linear programming (LP) can solve any flow problem and more, but generic LP solvers (simplex, interior point) are slower and less numerically stable than combinatorial flow algorithms. However, LP is necessary when constraints are not network-structured (e.g., arbitrary linear inequalities). For connectivity and reachability, simple BFS/DFS suffices; max flow is only needed when capacities matter.

In practice, start with the simplest algorithm that solves your problem. If you need only connectivity, use BFS. If you need bipartite matching with unweighted edges, use Hopcroft-Karp. If you need weighted assignment, consider Hungarian. Reserve full max flow for problems with arbitrary capacities, multiple constraints, or where the min cut itself is valuable. For min-cost problems, evaluate whether successive shortest paths with potentials will be fast enough or if you need cost scaling.

9. Common Mistakes and Best Practices

Even experienced engineers stumble on subtle pitfalls when implementing network flow algorithms. The most frequent error is failing to add reverse edges or incorrectly updating residual capacities. Every forward edge must have a reverse edge with zero initial capacity, and augmenting flow must symmetrically update both. Forgetting this prevents flow cancellation and yields suboptimal results that pass small tests but fail on adversarial cases.

Another common mistake is using DFS for Ford-Fulkerson without capacity scaling, leading to exponential time on graphs with large capacities (e.g., capacities 10^9). Always use Edmonds-Karp (BFS) or Dinic for guaranteed polynomial time. Similarly, using an adjacency matrix for sparse graphs with V = 10,000 wastes memory (100M entries) and causes cache misses; adjacency lists with edge objects are almost always superior.

Integer overflow is a silent killer: max flow values can exceed 32-bit int when capacities are large or numerous. Use Python's arbitrary precision integers or 64-bit types in other languages. Also, be careful with parallel edges — capacities should be summed, not overwritten, when building the graph.

Best Practices for Production Code

• Use adjacency lists with edge pooling: Store edges in arrays and reference by index to avoid object overhead and improve cache locality. Include fields for to, rev, and cap.
• Implement current-edge optimization: In Dinic's DFS, maintain a pointer per vertex to skip saturated edges, reducing the amortized cost per DFS to O(E).
• Add global relabeling for push-relabel: Periodically run BFS from sink to recompute exact heights; this can improve performance by orders of magnitude.
• Validate with min-cut: After computing max flow, verify that flow value equals cut capacity of reachable set in residual graph as a sanity check.
• Handle disconnected graphs: If s cannot reach t initially, max flow is zero — avoid unnecessary computation. Early exit if BFS level[t] == -1.
• Test with classic counterexamples: Use the 4-node graph where DFS Ford-Fulkerson takes 2000 iterations with capacities 1000 to ensure your implementation is not pseudo-polynomial.
• Consider using existing libraries: For production systems, libraries like NetworkX, LEMON, or Google OR-Tools are battle-tested and optimized in C++; custom Python is for learning or moderate sizes.

Finally, document capacity units and assumptions. Whether capacities represent bytes per second, requests per minute, or dollars, clarity prevents misinterpretation when the model is reused. Always profile with realistic graph sizes — asymptotic complexity hides constant factors that dominate at small scales.

10. Interview Questions

Network flow algorithms are a favorite in advanced technical interviews, especially for roles involving infrastructure, optimization, or graph theory. Interviewers test not just implementation but also modeling ability — can you recognize when a problem reduces to flow?

Q1: How would you find the maximum bipartite matching using max flow? What is the complexity?

Answer: Create a super-source s connected to all left vertices with capacity 1, connect left to right edges with capacity 1 for each original bipartite edge, and connect all right vertices to super-sink t with capacity 1. The max flow value equals the maximum matching size, and the edges with flow 1 between left and right constitute the matching. Using Dinic, complexity is O(E sqrt(V)) on unit networks, which matches Hopcroft-Karp. Be prepared to code this reduction and explain why capacity 1 enforces matching constraints (each vertex matched at most once).

Q2: Explain why Ford-Fulkerson with DFS can be exponential and how Edmonds-Karp fixes it.

Answer: DFS may repeatedly augment along paths that differ by only one edge, sending only 1 unit per iteration if capacities are large but bottleneck is 1 due to alternating choices. Example: s->A 1000, s->B 1000, A->B 1, A->t 1000, B->t 1000; DFS alternating A->B causes 2000 iterations. Edmonds-Karp always picks the shortest path (fewest edges) via BFS, guaranteeing distance labels monotonically increase and each edge becomes critical O(V) times, yielding O(VE^2) independent of capacities. This demonstrates understanding of pseudo-polynomial vs strongly polynomial.

Q3: Given a flow network, how do you find the minimum s-t cut after computing max flow?

Answer: Run BFS/DFS from s in the residual graph Gf (using only edges with residual capacity > 0). The set S of reachable vertices defines the cut (S, V-S). This cut is minimum and its capacity equals max flow. To list cut edges, iterate over all original edges (u,v) where u in S and v not in S and sum their capacities. This also identifies bottlenecks. Follow-up: how to find all edges that can be in some min cut? Answer involves strongly connected components of residual graph.

Q4: How do you handle vertex capacities or lower bounds on edges?

Answer: For vertex capacity c(v), split v into v_in and v_out with edge v_in -> v_out capacity c(v); redirect incoming edges to v_in and outgoing from v_out. For lower bounds l(u,v) <= f(u,v) <= c(u,v), set initial flow to l, compute node demands (inflow - outflow), add super-source/sink to satisfy demands with additional edges of capacity c-l, and check if max flow saturates all demand edges. This tests ability to transform variants to standard max flow.

Q5: Design a system to assign 10,000 tasks to 1,000 servers with capacity constraints and minimize cost. Which algorithm would you use?

Answer: Model as min-cost max-flow: source to tasks (capacity 1, cost 0), tasks to servers (capacity 1, cost = assignment cost), servers to sink (capacity = server capacity, cost 0). Then run successive shortest augmenting path with potentials (Dijkstra + Johnson) to send flow = number of tasks. Complexity O(F * (E log V)) where F=10,000. Discuss alternatives: Hungarian if one-to-one, or greedy if approximate solution acceptable. Mention scaling and capacity considerations, and that for pure max throughput without costs, Dinic suffices. This evaluates system design and tradeoff reasoning.

Mastering these questions requires both coding fluency and the ability to articulate reductions, complexity tradeoffs, and practical heuristics — the hallmarks of a strong candidate for graph-heavy roles.