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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.