2022-117

The push-relabel algorithm is one of many known algorithms used to find maximum flows. Consider the following statements about the push-relabel algorithm:

1. The push–relabel algorithm is one of the most efficient maximum flow algorithms. It allows the flow to exceed the edge's flow capacity, except from the source. It pushes as much flow as possible, and in the end, it saturates all edges from the source.
2. The push-relabel algorithm first steps are: Start with initial flow as zero, and then find augmenting paths and add them to the flow. When no more augmenting paths exist, return the resulting flow.
3. The push-relabel algorithm uses a labeling function to assign heights to the nodes, determining which ones should be selected for the push operation.
4. There is an implementation of the push-relabel algorithm that is called Edmonds-Karp algorithm. This implementation uses Breadth-First Search, which reduces the time complexity of the original algorithm.
5. Another differential from the push-relabel algorithm is that it also requires the construction of the level graph of the residual network.
   

Select the option that exactly list the correct statements:

1. I, II and III are correct.
2. I, III, IV and V are correct.
3. I and IV are correct.
4. I and III are correct.
5. None of the above.

Original idea by: Heitor Mattosinho