I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed and edge weights are all integers. I can find the maximum flow the first time, by Ford-Fulkerson's algorithm or some variant, but at each step thereafter it would be great if I could use a different (faster) algorithm to find the max flow. At each step, only one of the edge weights is changed, and it is only changed by a value of +1 or -1. What sort of algorithm could do this incremental update for me? It needs to be faster than recomputing the max flow from scratch. It could also be two separate algorithms (but similar I would hope): one for the incrementing case and one for the decrementing case. Thanks in advance for the help!

I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of the edges). I am wondering how that can be possible. Can we choose augmenting paths that allow us to never "push back"?

I stumbled across this question and answer (source): Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow. Answer: First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|)) and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting path would mean the solution is not a maximum flow. Does this mean that the Ford-Fulkerson algorithm will reach max flow if given any valid flow as input, instead of initializing all edges to 0 at the start?

According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how can this be the max flow?

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut (by flood-filling outward from s along any edges or reverse edges with left-over capacity), it seems the same cut is obtained regardless of which flow-graph you use. Is this true? Is there a way to iterate over all cuts such that each iterator-step requires only polynomial time?