Given a graph, for every pair of vertices s,t find the max flow that can be sent from s to t, if every vertex and edge has unit capacity, and every edge an infinite (very big) negative cost, we’ll get the longest path from s to t. Since MCMF Is P, therefore P=NP. QED
If you can’t find the bug in the previous algorithm, send me my Millennium Prize.
PS. do you know some other P=NP proofs?
When you try to find an augmenting path you apply dijkstra or something like that to find the minimum cost path, but with negative costs you would need to explore every possible path, right?
I think MCMF only works on graphs without negative cycles, and the algorithm does not guarantee that no negative cycles will be created from the original graph.
I think you cannot remove negative edge cycles if cost is -infinity.
And hence MCMF cannot be applied.
The condition vertices with unit capacities was intended to make you think that there should not be cycles with negative cost carryng flow.