Network Flow and Integer Linear programming

Question

We all know that the problem of network flow can be reduced to linear programming. However, when we solve network flow problem, we need the flow to be integer all the time. So I think network flow should be reduced to integer linear programming. Because of ILP which is NP-complete, the network flow problem should be NP-complete problem too. But this contradicts what we learned since the running time of network flow is O(Cm)! Where am I wrong? Is it because network flow problem’s running time is pseudo-polynomial time like knapsack problem(Wn)? I am so confused now!

Answer 1

You still technically have to show that the reduction takes polynomial time, but that is a more minor issue here. The main issue is that your reduction is the wrong way around.

To show that something is NP-complete, you need to do two things:

1. Show that it is in NP
2. Show that it is also NP-hard.

To do the latter using reductions, you need to reduce ILP to network flow, not reduce network flow to ILP. The point of the reduction is to show that you could solve ILP (and by extension, every NP problem) in polynomial time if you could solve your given problem (in this case, network flow). By reducing the wrong way, you've actually shown that you can solve network flow in polynomial time if you could solve ILP in polynomial time (which is true but useless since network flow is in P).