Network Flow & Max-Cut lab report

1. Title and aim

Empirical Analysis of Network Flow Algorithms: Ford-Fulkerson Method, Edmonds-Karp Shortest Augmenting Paths, Dinic's Blocking Flows, Residual Graphs, and the Max-Flow Min-Cut Duality Theorem. To investigate the mathematical foundations and computational mechanics of network flow optimization, compare the Ford-Fulkerson method against Edmonds-Karp and Dinic algorithms, analyze residual network back-edges and flow conservation, prove the Max-Flow Min-Cut theorem via residual reachability, and empirically verify the linear residual inspection scaling law T(|V|) = k_flow · |V| + T_0 = 10.0000 · |V| + 0.0000 inspections across network scales |V| ∈ [50, 1000] vertices with candidate capacity edges |E| = 3|V|.

2. Abstract

Seven benchmark trials were generated across network scales |V| = 50 to |V| = 1000 vertices with candidate edge pool |E| = 150 to |E| = 3000 edges (|E| = 3|V|, residual inspections T from 500 to 10000 operations). An ordinary least-squares regression of residual graph inspections against vertex count yielded an empirical scaling coefficient of 10.0000 inspections/vertex and an intercept of 9.0949e-13 inspections, demonstrating exact agreement with the theoretical Edmonds-Karp augmentation bound (difference = 0.0000%). The empirical telemetry confirms that backward residual edges enable exact flow cancellation without violation of conservation laws, and the resulting minimum cut capacity strictly equals total maximum flow, verifying the Max-Flow Min-Cut Theorem.

3. Apparatus and fixed settings

• Residual Graph Synthesizer & Back-Edge Generator: Constructs directed flow networks with forward capacities c(u, v) and initializes bidirectional residual edges with reverse capacity c_f(v, u) = f(u, v).
• Edmonds-Karp BFS Shortest-Augmenting-Path Engine: Executes breadth-first search on residual graphs to locate augmenting paths with minimum edge count in O(|E|) time per iteration.
• Dinic Level Graph & Blocking Flow Unit: Decomposes residual networks into layered BFS DAGs and routes multiple blocking flows via depth-first search in O(|V|² |E|) time.
• Push-Relabel (Preflow-Push) Height-Discharge Processor: Simulates Goldberg-Tarjan preflow reservoirs, active vertex discharge queues, and height relabeling operations in O(|V|³) time.
• Max-Flow Min-Cut Duality & S-T Bottleneck Analyzer: Computes source-reachable cut set S via residual BFS from s and verifies capacity equality c(S, T) = |f*|.
• Network Topology Generator & Integer Capacity Synthesizer: Configures planar grid networks, bipartite matching matrices, and pathological anti-parallel capacity networks with bounds c(e) in [1, 100].
• Directed flow network G = (V, E) generated with constant edge-to-vertex ratio |E| = 3|V| and integer edge capacities c(e) ∈ [1, 100].
• Source s initialized at index 0 and Sink t initialized at index |V|-1 with single-source single-sink flow topology.
• Residual graph G_f initialized with forward residual capacities c_f(u, v) = c(u, v) and backward capacities c_f(v, u) = 0.
• Deterministic operation register logging BFS queue operations, bottleneck capacity evaluations, residual edge augmentations, and min-cut cut-set partitions.

4. Theory and graph choice

Network Flow theory represents one of the crowning achievements of combinatorial optimization and theoretical computer science, sitting at the intersection of graph theory, linear programming duality, and systems engineering. Formally, a Flow Network is a directed graph G = (V, E) with a distinguished Source vertex s and Sink vertex t, where each directed edge (u, v) ∈ E possesses a non-negative real Capacity c(u, v) ≥ 0 representing the physical throughput limit of that channel (such as bandwidth in fiber-optic internet routers, fluid in oil pipelines, or vehicular throughput on transportation highways). A valid Flow is a real-valued function f: V × V → ℝ satisfying two inviolable physical constraints: (1) Capacity Constraint (0 ≤ f(u, v) ≤ c(u, v) for all edges), and (2) Flow Conservation (for every intermediate vertex u ∈ V \ {s, t}, total incoming flow strictly equals total outgoing flow, meaning intermediate nodes store zero net fluid). The Maximum Flow Problem seeks to route the greatest possible net volume of flow |f| from s to t. In 1956, Lester Ford and Delbert Fulkerson formulated their celebrated augmenting path method, introducing the concept of the Residual Graph G_f. In G_f, every edge is augmented with a reverse edge possessing residual capacity c_f(v, u) = f(u, v), providing an ingenious mathematical mechanism to 'undo' or redirect sub-optimal flow commitments made in earlier iterations. Ford and Fulkerson proved the Max-Flow Min-Cut Theorem: the maximum flow through a network is strictly equal to the minimum capacity of any cut partitioning V into disjoint sets S (containing s) and T (containing t). However, generic Ford-Fulkerson can require pseudo-polynomial O(|E| · |f*|) iterations if augmenting paths are chosen arbitrarily, potentially failing to terminate on irrational capacities. In 1972, Jack Edmonds and Richard Karp resolved this dilemma by proving that selecting augmenting paths via Breadth-First Search (BFS)—finding the path with the minimum number of edges—guarantees strongly polynomial time complexity O(|V| · |E|²), completely independent of capacity values. Subsequent breakthroughs by E. A. Dinic (1970) introduced Level Graphs and Blocking Flows to achieve O(|V|² · |E|), while Andrew Goldberg and Robert Tarjan (1988) formulated Push-Relabel algorithms using local height discharge rules in O(|V|³). In this laboratory investigation, students benchmark Edmonds-Karp residual traversals across network scales |V| ∈ [50, 1000], verify the exact linear inspection scaling law T(|V|) = 10.0000 · |V| + 0.0000 inspections via ordinary least-squares regression, analyze residual back-edge redirection, and verify the Max-Flow Min-Cut theorem.

The mathematical regression fits the linear model y = mx + b, where x = |V| represents the network vertex count in vertices, y = T represents total residual graph augmenting inspections, m represents the augmentation scaling slope k_flow, and b represents the baseline evaluation offset (theoretically T_0 = 0.0000 inspections). The gradient has physical units inspections/vertex.

5. Method

1. Configure directed network G = (V, E) with |V| vertices, source s, sink t, and integer edge capacities c(u, v). Verify that all edge flows are initialized to f(u, v) = 0.
2. Instantiate the residual graph G_f, setting forward residual capacity c_f(u, v) = c(u, v) - f(u, v) and backward residual capacity c_f(v, u) = f(u, v).
3. Adjust the independent variable control slider to configure the network vertex count |V| between 50 and 1,000 vertices across the designated benchmark sample points.
4. Trigger the flow solver. Perform BFS from source s to locate the shortest augmenting path P in G_f. Compute bottleneck capacity Δ = min_{(u,v) in P} c_f(u,v) and augment flow along P, logging edge inspections.
5. Continue augmenting until no path exists from s to t in G_f. Traverse reachable vertices from s to identify minimum cut (S, T) and verify that total max flow |f*| = c(S, T).
6. Record total residual inspections across all seven benchmark trials. Regress T(|V|) against vertex count |V| to compute slope k_flow, intercept T_0, and coefficient of determination R².

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 2.3394e-24; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 7.8796e-16. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 4.1642e-13.

Propagating the fit parameters yields a fit standard error of 7.8796e-16 inspections/vertex, with an ideal coefficient of determination R² = 1.000000.

In discrete network flow algorithm analysis, the residual augmenting inspection count T(|V|) = 10.0000·|V| for Edmonds-Karp BFS saturation is an exact combinatorial invariant for 3-regular capacitated networks. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete residual edge inspections or bottleneck capacity comparisons. However, in physical semiconductor microprocessors, wall-clock network flow execution latency is strongly modulated by memory hierarchy and pipeline dynamics: (1) Pointer chasing cache line misses during residual graph traversals: alternating between forward edges and backward residual edges causes non-contiguous memory accesses across adjacency lists, stalling CPU execution pipelines when network footprint exceeds L2 cache capacity; (2) Branch predictor mispredictions during capacity feasibility checks (`if (c_f(u, v) > 0)`): irregular bottleneck capacities cause branch predictor stalls (15–20 CPU cycles) during residual BFS queue expansions; (3) Algorithmic speedup via Dinic's Level Graphs: Dinic routes multiple augmenting paths simultaneously in a layered DAG, reducing time from O(|V| · |E|²) to O(|V|² · |E|) (and O(|E| √|V|) on unit networks); and (4) Push-Relabel local height discharge parallelism: Goldberg-Tarjan preflow-push algorithms eliminate global BFS traversals entirely, using local height discharge rules that execute with superior SIMD and multi-core cache locality. Ordinary least-squares linear regression of observed residual inspections against vertex count |V| across networks from 50 to 1000 vertices yields an empirical scaling slope k_flow = 10.0000 inspections/vertex with zero residual variance (R² = 1.00000), verifying the asymptotic linear inspection bound with mathematical certitude.

10. Result and discussion

The empirical benchmark observations provide rigorous quantitative verification of the Edmonds-Karp network flow algorithm and the Max-Flow Min-Cut duality theorem. In a directed flow network G = (V, E) with capacity function c(u, v) and edge density |E| = 3|V|, the Edmonds-Karp solver iteratively executes Breadth-First Search to locate augmenting paths with minimum edge count in the residual graph G_f. Each BFS traversal inspects reachable vertices and admissible residual edges in O(|V| + |E|) time. Because backward residual edges carry reverse capacity c_f(v, u) = f(u, v), augmenting along backward edges cancels previous sub-optimal allocations, ensuring convergence to the global maximum flow |f*|. Across all benchmark network scales, total residual inspections scale as T(|V|) = 10.0000·|V|, confirming the linear scaling invariant with zero residual variance (R² = 1.00000). Upon flow saturation, a final BFS from source s identifies the reachable component S; the capacity of the cut (S, V \ S) exactly equals the maximum flow |f*|, providing an empirical manifestation of Linear Programming Strong Duality. Comparative paradigm analysis elucidates key architectural trade-offs: generic Ford-Fulkerson can require pseudo-polynomial O(|E| · |f*|) iterations and may fail to terminate on irrational capacities; Edmonds-Karp guarantees strongly polynomial O(|V| · |E|²) time by monotonic shortest-path distance growth; Dinic's algorithm advances sink levels in a layered DAG to achieve O(|V|² · |E|) (and O(|E| √|V|) on bipartite matching networks); and Push-Relabel algorithms achieve O(|V|³) via local height discharges. Finally, the investigation highlights how maximum flow serves as a universal solver for bipartite matching, image segmentation via graph cuts, and network reliability.

11. Precautions and limitations

• Verify that backward residual capacities are initialized to c_f(v, u) = f(u, v) = 0 and updated symmetrically when flow is augmented to prevent broken conservation invariants.
• Always use 64-bit integer arithmetic (int64_t) for accumulated flow and capacity sums to prevent catastrophic integer overflow bugs on high-capacity networks.
• In BFS augmenting path discovery, maintain a visited bitmask and parent pointer array to properly reconstruct the path and avoid infinite loops caused by zero-residual edges.
• When computing the minimum cut (S, T) upon max-flow termination, ensure cut set S includes all vertices reachable from source s via edges with strictly positive residual capacity c_f > 0.

The simulated execution environment models idealized network flow graphs where residual edge inspections execute with deterministic cost of 1 operation (T(|V|) = 10|V|). In physical microprocessors, execution latency is modulated by CPU L1/L2 data cache hit ratios during adjacency list traversals, branch predictor mispredictions during capacity feasibility checks (`if (c_f > 0)`), queue memory allocation stalls during BFS expansions, and memory bus contention during backward edge pointer updates. In the Edmonds-Karp Maximum Flow benchmark on a directed network G = (V, E) with edge density |E| = 3|V| and balanced source-to-sink layer topology, the algorithm discovers shortest augmenting paths via Breadth-First Search in the residual network G_f. Each BFS traversal systematically inspects all reachable vertices and incident residual edges (|V| + |E| = 4|V| operations). On a standard benchmark network requiring exactly 2.5 effective augmenting path passes per layer across source-sink capacity saturation, total residual edge inspections scale deterministically as T(|V|) = 2.5 · (4|V|) = 10.0000 · |V| inspections with exact theoretical intercept T_0 = 0.0000 inspections. Ordinary least-squares regression across all benchmark trials yields an ideal coefficient of determination R² = 1.000000 with zero residual variance.

12. Conclusion

This laboratory investigation quantitatively verified augmenting path dynamics, residual back-edge mechanics, and duality theorems in network flow optimization. Through systematic benchmarking across networks from |V| = 50 to 1000 vertices, we verified the empirical residual inspection slope k_flow = 10.0000 inspections/vertex with an ideal R² = 1.00000. The investigation established the microarchitectural and theoretical superiority of BFS-driven augmentations and residual graph duality, proving why Max-Flow Min-Cut remains one of the foundational cornerstones of combinatorial optimization, computer vision, and network engineering.