Neural Sync Active

Applications of Network Flow

Registry Synced

Applications of Network Flow

925 words

5 min read

Reading compass

Now · 🎯 Learning Objectives

Applications of Network Flow

🎯 Learning Objectives

Model real-world problems as flow networks
Apply max-flow min-cut to bipartite matching
Solve scheduling with flow networks
Analyze baseball elimination using min-cut
Formulate project selection as flow

1. Bipartite Matching

1.1 Problem

Given bipartite graph

G = (U \cup V, E)

, find maximum matching (largest set of edges with no shared vertices).

1.2 Flow Formulation

Add source

s

connected to all

u \in U

(capacity 1), all

v \in V

connected to sink

t

(capacity 1). Set all edges

u \to v

with capacity 1. Max flow = max matching size. (Diagram)

1.3 Tracing

Iteration	Augmenting Path	Flow Added	Matching
1	s→u1→v1→t	1	(u1,v1)
2	s→u2→v2→t	1	(u1,v1), (u2,v2)
3	s→u3→v3→t	1	(u1,v1), (u2,v2), (u3,v3)

Max matching = 3 (perfect matching).

2. Scheduling with Release Times and Deadlines

2.1 Problem

n

jobs, each with processing time

p_i

, release time

r_i

, deadline

d_i

. Can all jobs be scheduled on a single machine?

2.2 Flow Construction

Time slots: discretize into unit slots between min $r_i$ and max $d_i$
Source → each job: capacity $p_i$
Each job → eligible slots: capacity 1
Each slot → sink: capacity 1
Feasible schedule exists iff max flow = $\sum p_i$

3. Baseball Elimination

3.1 Problem

Which teams are mathematically eliminated from playoff contention? Flow construction: For each remaining game between teams

i

and

j

, create game node

g_{ij}

with edge from source (capacity = games remaining). Each game connects to team nodes (capacity ∞). Team nodes connect to sink with capacity = wins team

i

can still have without exceeding team

x

's max. Cut interpretation: If min-cut < total remaining games, team

x

is eliminated.

3.2 Tracing Example

Team	Wins	Games Left	vs. A	vs. B	vs. C
A	50	10	—	4	6
B	48	10	4	—	6
C	47	10	6	6	—
D	44	10	5	5	0

Can team D (44 wins) still win? Max wins D can achieve = 44 + 10 = 54. But will some other team exceed 54?

4. Project Selection

4.1 Problem

Projects with revenue

p_i

(profit if > 0, cost if < 0). Some projects require others as prerequisites. Select feasible set maximizing profit.

4.2 Reduction to Min-Cut

(Diagram)

Source → profitable projects: capacity = revenue
Costly projects → sink: capacity = |cost|
Prerequisite edges: capacity = ∞
Selected projects = reachable from source in min-cut

5. Common Pitfalls

Pitfall 1: Wrong Capacity Assignment

The mistake: Setting edge capacities incorrectly, allowing infeasible flows. Correct approach: Each unit of flow should represent one unit of resource (job, match, slot). Verify flow corresponds to valid solution.

Pitfall 2: Missing Intermediate Nodes

The mistake: Connecting source directly to sink without game/job nodes. Correct approach: Model constraints as intermediate nodes. Game nodes ensure each game result is assigned exactly once.

Pitfall 3: Infinite Capacity on Wrong Edges

The mistake: Using ∞ capacities constrain the cut improperly. Correct approach: Only prerequisite edges should have ∞ capacity (must be selected together). Player/slot capacities must be finite.

6. Key Concepts Reference

Application	Flow Model	Key Insight
Bipartite matching	Unit capacities	Flow = matching size
Scheduling	Job→slot edges	Feasibility via max flow
Baseball elimination	Game→team nodes	Min-cut = elimination proof
Project selection	Source→profit, cost→sink	Max profit = total revenue - min cut
Image segmentation	Source=foreground, sink=background	Min-cut = optimal segmentation

7. 📝 Practice Questions

Q1: A bipartite graph has U={a,b,c}, V={1,2,3}. Edges: a-1, a-2, b-2, b-3, c-1, c-3. Find maximum matching.

Answer: Max matching = 3. Possible matching: (a,1), (b,2), (c,3). All three vertices on both sides matched (perfect matching). Flow formulation would find this in 3 augmentations. Q2: What does the min-cut in the baseball elimination graph represent?

Answer: The min-cut represents a set of teams that must exceed team x's wins. If Team A and B are on the source side of the cut, ALL remaining games between A and B must go to A or B (cannot go to x's side). The cut capacity = wins A/B must get + remaining games involving them. If this capacity < total remaining games, some wins must go to x's opponents, meaning x is eliminated. Q3: For project selection with profits [5, -3, -2, 4] and prerequisites: 1→3, 2→3, 3→4, find optimal selection.

Answer: Flow model: s→1 (5), s→2 (0 since 2 not profitable... wait, 2 has 0 profit? No -2 is a cost). Actually: P1=5, P2=-3, P3=-2, P4=4. Source connects to P1(5) and P4(4). P2 connects to sink(3), P3 connects to sink(2). Prereq: P1→P3, P2→P3, P3→P4. Min cut determines optimal set. Projects reachable from source in min cut are selected. Q4: How does max flow find the min cut?

Answer: After max flow is found, BFS from source along edges with residual capacity > 0. The reachable set = S side of min cut. T side = all other vertices. The min-cut capacity equals max flow value (max-flow min-cut theorem). This also finds the bottleneck edges. Q5: Can all NP problems be solved with network flow?

Answer: No — flow is in P (solvable in polynomial time). Only problems that can be formulated as flow are efficiently solvable. NP-complete problems (like general TSP, 3SAT) cannot be expressed as pure flow networks without exponential blowup. However, flow is a subroutine in approximation algorithms for some NP-hard problems.

8. 🔗 Cross-References

Week 4 - Network Flow: Ford-Fulkerson, max-flow min-cut
Week 6 - NP-Completeness: Limits of flow
BSCS4020 (DSA): Graph algorithms Join Discord PreviousNetwork FlowNextString Algorithms