A Characterization of Irreducible Infeasible Subsystems in Flow Networks

Infeasible network flow problems with supplies and demands can be characterized via violated cut-inequalities of the classical Gale-Hoffman theorem. Written as a linear program, irreducible infeasible subsystems (IISs) provide a different means of infeasibility characterization. In this article, we answer a question left open in the literature, by showing a one-to-one correspondence between IISs and Gale-Hoffman-inequalities in which one side of the cut has to be weakly connected. We also give a polynomial-time algorithm that computes some IIS using a single max-flow computation and show strong NP-hardness of finding an IIS of minimal cardinality in this special case.

Article

Download

View A Characterization of Irreducible Infeasible Subsystems in Flow Networks