algorithm - Network Flow Update Values -

i practicing algorithms problems book , came across one:

you given directed network g n nodes , m edges, source s, sink t , maximum flow f s t. assuming capacity of every edge positive integer, describe o(m + n) time algorithm updating flow f in each of following 2 cases.

(i) capacity of edge e increases 1.

(ii) capacity of edge e decreases 1.

it seems simple walking through network flow edges , adjusting flows, not think simple. wikipedia give algorithms o(n^2 m) or o(n m^2). or thoughts appreciated.

there solution here.

suppose e edge between u , v.

increased capacity

the idea increasing capacity dfs in residual flow graph path s t.

decreased capacity

if edge unsed in maximum flow done.

otherwise, idea see if there alternative path u v in residual flow graph. takes o(n+m). if found, can increase maximum flow 1.

otherwise, need decrease flow. finding path u s along flow can increase 1, , path t v along flow can increase 1. (the increases in reverse direction reduces flow s t).