A polynomial multicommodity flow problem with difficult path generation

In the paper we consider a commonly known network design problem with demand restoration assuming stub release. No compact linear programming (LP) formulation for the problem is known, and all known non-compact LP formulations of the problem require NP-hard path generation (pricing). Therefore, the problem itself is suspected to be NP-hard - this, however, is not actually known. The main result of our paper reveals a special case of the basic problem for which the resulting non-compact LP formulation still has an NP-hard pricing problem, the corresponding compact LP formulation is not known either, but the problem itself is polynomial. The considered special case assumes only one failing link so that all the links but one are assumed to be 100% reliable. The constructed case of a polynomial multicommodity flow problem with difficult path generation is of interest since no such problem is, to the best of our knowledge, widely known.