KMW revisited in a graph theoretic way

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?