MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A flow network has source ss, sink tt, and two parallel routes: s→a→ts\to a \to t with c(s,a)=3c(s,a)=3, c(a,t)=2c(a,t)=2, and s→b→ts \to b \to t with c(s,b)=2c(s,b)=2, c(b,t)=2c(b,t)=2 (current maximum flow 44). What is the smallest increase to c(a,t)c(a,t) alone that raises the maximum flow to 55?