As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
1 Answer
$\begingroup$
$\endgroup$
Integer multi-commodity flow is indeed NP-complete, as stated in the corresponding Wikipedia article (link to the reference paper).
However, your reasoning is incorrect. If ILP is NP-complete and some problem X reduces to ILP, it does not mean that X is NP-complete. In order to show NP-completeness of X via ILP (or any other NP-complete problem) you need to provide the reduction in the opposite direction — from ILP to X: that is, given an arbitrary ILP instance, convert it to a network such that finding the multi-commodity flow in that network will give the solution to the original ILP instance.
NB. Just to clarify: you can replace NP-complete with NP-hard in the above explanation. NP-completeness means both being NP-hard and belonging to NP, and showing the latter is trivial for mentioned problems.
