Problem#1: finding null weight cycles in a dynamic/periodic graph
This problem has many approaches. The interesting ones are the following:
1. Karp-Miller-Winograd's decomposition using LP formulation
2. Kosaraju-Sullivan's decomposition using O(n\log n \times Z) with (n: number of vertices of PRDG and Z the complexity of a LP program)
3. Darte-Vivien using a the idea of decomposition similar to KMW and improving the complexity given by KS to O(n\times Z)
Cohen-Megiddo: seem to give a formulation similar to LP?
Problem#2: The Max-flow problem
1. People first gave an LP formulation.
2. Edmonds-Karp have a graph theoretic algorithm: O(n^2\times m)
3. Tarjan improved it to unbeatable level.
A similar statement can be given to any of the three main problems dealt in Tarjan's book (MST, Path-problem or max-flow)
Question: What can be done so that Problem #1 can be made as Problem#2?
Now, what about Cohen-Megiddo for problem#1? Do they use some kind of LP formulation?
What about Orlin's 1984 paper?
What about Orlin's paper on simplex?
What about Megiddo's simplex paper?