MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

A flow network has source ss, sink tt, and vertices a,b,ca,b,c with capacities c(s,a)=5c(s,a)=5, c(s,b)=3c(s,b)=3, c(a,c)=2c(a,c)=2, c(b,c)=2c(b,c)=2, c(c,t)=4c(c,t)=4 (current maximum flow 44). What is the smallest TOTAL increase, split between c(a,c)c(a,c) and c(c,t)c(c,t) in whatever way works best, needed to raise the maximum flow to 66?