ADVANCED ALGORITHMS - NETWORK FLOW:Network Flow Applications: Matching, Scheduling, Image Segmentation

Network Flow Applications

The power of network flow lies in its generality. Dozens of important problems reduce elegantly to max-flow or min-cost flow. Mastering this reduction technique is essential for competitive programming and system design.

1. Bipartite Matching

Problem: Given a bipartite graph G = (L ∪ R, E), find a maximum matching (no two edges share an endpoint).

Reduction:

• Add super-source S with edges to every left vertex (capacity 1)
• Add super-sink T with edges from every right vertex (capacity 1)
• Original edges get capacity 1
• Max flow = max matching

def max_bipartite_matching(left_size, right_size, edges):
    """
    Maximum bipartite matching via max-flow (Dinic's in O(E * sqrt(V))).
    
    Nodes: 0=source, 1..left_size=left, left_size+1..left+right=right, last=sink
    """
    n = left_size + right_size + 2
    source = 0
    sink = n - 1
    
    g = MaxFlowDinics(n)
    
    # Source to all left vertices
    for l in range(1, left_size + 1):
        g.add_edge(source, l, 1)
    
    # All right vertices to sink
    for r in range(left_size + 1, left_size + right_size + 1):
        g.add_edge(r, sink, 1)
    
    # Original bipartite edges
    for l, r in edges:
        g.add_edge(l, left_size + r, 1)
    
    return g.max_flow(source, sink)

# Hall's theorem: a bipartite graph has a perfect matching iff
# for every subset S of L, |N(S)| >= |S| (neighborhood is large enough)

König's Theorem: In bipartite graphs, maximum matching = minimum vertex cover. This connects flow (matching) to LP duality and the min-cut.

2. Edge-Disjoint Paths

Problem: Find the maximum number of paths from s to t that share no edges.

Reduction: Set all edge capacities to 1. Max flow = max number of edge-disjoint paths.

Vertex-disjoint paths: "Split" each vertex v into v_in and v_out with an edge of capacity 1 between them. Edges go into v_in and out of v_out.

def vertex_disjoint_paths(n, edges, source, sink):
    """
    Maximum vertex-disjoint s-t paths via node-splitting.
    2n nodes: node v becomes v_in (v) and v_out (v + n).
    """
    g = MaxFlowDinics(2 * n)
    
    # Internal edges: v_in → v_out with capacity 1 (except source/sink: use n)
    for v in range(n):
        cap = n if (v == source or v == sink) else 1
        g.add_edge(v, v + n, cap)
    
    # Original edges: u_out → v_in with capacity n (unlimited)
    for u, v in edges:
        g.add_edge(u + n, v, n)
        g.add_edge(v + n, u, n)  # undirected
    
    return g.max_flow(source, sink + n)

3. Task Assignment with Capacity Constraints

Problem: Assign n jobs to m machines. Job j can run on machine i (given as a set of valid pairs). Each machine i can handle at most d[i] jobs simultaneously.

def job_assignment(n_jobs, n_machines, valid_pairs, machine_capacity):
    """
    Maximum job assignment with machine capacity constraints.
    Source → job (cap 1) → machine (cap 1) → sink (cap machine_capacity[m])
    """
    source = 0
    sink = n_jobs + n_machines + 1
    g = MaxFlowDinics(sink + 1)
    
    for j in range(n_jobs):
        g.add_edge(source, j + 1, 1)
    
    for m in range(n_machines):
        g.add_edge(n_jobs + 1 + m, sink, machine_capacity[m])
    
    for j, m in valid_pairs:
        g.add_edge(j + 1, n_jobs + 1 + m, 1)
    
    return g.max_flow(source, sink)

4. Project Selection (Profit Maximization)

Problem: n projects with profits p[i] (can be negative). m resources with costs c[j]. Project i requires resource j (edges). Select projects to maximize net profit.

Reduction (project selection / closure problem):

• Source S → project i with capacity p[i] if p[i] > 0
• Project i → sink T with capacity −p[i] if p[i] < 0
• Resource j → sink T with capacity c[j]
• Project i → resource j (dependency) with capacity ∞

Max profit = Σ max(0, p[i]) − min_cut(S, T)

5. Circulation with Demands

Problem: Each edge has both lower bound l(e) and upper bound c(e) on flow. Does a feasible circulation exist?

Reduction:

1. For each edge (u, v, l, c): add edge (u, v, c − l) to new graph
2. Add super-source S and super-sink T
3. For each node v: let excess = Σ l(in-edges) − Σ l(out-edges)

• If excess > 0: add edge (S, v, excess)
• If excess < 0: add edge (v, T, −excess)

1. A feasible circulation exists ↔ max flow from S to T saturates all edges from S

Identifying Network Flow Problems

A problem likely reduces to network flow if it involves:

• Routing or matching between two "sides"
• Capacities on edges or nodes
• Maximum/minimum over a sum or count
• Conservation constraints (flow in = flow out)
• Cuts separating source from sink

Practice Problems

1. Solve a task-scheduling problem where nurses must be assigned to shifts with hospital capacity constraints
2. Find max-flow in a network and extract the actual matching (not just the count)
3. Given a bipartite graph, find both a maximum matching AND the minimum vertex cover (König's theorem)
4. Design a flow network to solve "at least k edge-disjoint paths exist" as a decision problem
5. Model the "project selection" problem and solve on a small example