Question

Suppose someone presents you with a solution to the max-flow problem on some network. Give a linear-time algorithm to determine whether the solution does indeed give a maximum flow.

Short answer

Ford-Fulkerson algorithm is the linear time algorithm that determines if the solution obtains a maximum flow.

Step-by-step solution

Explain Maximum flow

Consider a network that consists of a directed graph with source and sink nodes. Each edge of the directed graph has its capacity denoted by $\mathrm{c}$. The value of the edge capacity must be greater than zero.The maximum flow aims to send as much data as possible from source to sink. The maximum flow should not exceed the capacity of any of the edges, and the amount of entering flow must be equal to leaving flow.

Give a linear time algorithm to determine the maximum flow. 

The Linear time algorithm works sequentially for each edge to find the flow. The flow begins with the initial value of zero. Augmented path is the path that satisfies the maximum flow constraints. For each augmented path, flow is added sequentially path-wise.

Ford-Fulkerson algorithm:

Source s,

Sink t,

$initialflow\to 0$

While augmented path

Add path

Return flow

The above algorithm runs in linear time to find the maximum flow.

Therefore, the Ford-Fulkerson algorithm is the linear time algorithm that determines whether the solution gives a maximum flow.