More pathological examples for network flow problems

Two examples are presented. The first example is bad for a large subset of the primal minimum cost flow algorithms, namely those algorithms which start with the required amount ofs – t flow distributed in a feasible, but nonoptimal manner, and which get optimal by sending flow about negative cycles. In particular, the example is bad for the primal method which always sends flow about a cycle which yields the largest decrease in the objective function.The second example requires O(n ³) flow augmentations using tie-breaking variants of either the Edmonds—Karp shortest path or fewest reverse arcs in path maximum flow algorithms. This example implies that it is not possible to substantially improve the performance (in a worst case sense) of either algorithm by resolving ties.