I am struggling with the understanding of the (quite famous) paper on lexicographical flows:
Maximal, Lexicographic, and Dynamic Network Flows - by Edward Minieka
The definition of the problem seems really similar to a multi-commodity flow problem. Specifically, instead of the demands constraint, there seems to be a more general (and permissive) one.
I can't really get how the multi-commodity flow problem is NP-complete, while formulation by Minieka is polynomially solvable.
I feel like I am missing something on the purpose of this paper. What does it mean with "departure pattern". Can't I, indeed, always find such a "pattern" within multi-commodity formulation? Doesn't this make any multi-commodity flow problem polynomially solvable?
I am sorry if my question is a bit confusing, but the world of network problems is huge and it's really hard for me to keep it rigor.
