A Characterization of Irreducible Infeasible Subsystems in Flow Networks

作者：Joormann Imke; Orlin James B; Pfetsch Marc E^*

来源：Networks, 2016, 68(2): 121-129.

DOI：10.1002/net.21686

• flow network
• irreducible infeasible subsystem
• Gale-Hoffman theorem
• infeasibility analysis
• witness
• max flow-min cut
• NP-hardness

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 show that a single max-flow computation allows one to compute an IIS. Moreover, we prove that finding an IIS of minimal cardinality in this special case of flow networks is strongly NP-hard.

• 出版日期2016-9
• 单位MIT