A characterization of irreducible infeasible subsystems in flow networks. Issue 2 (28th June 2016)

• Record Type: Journal Article
• Authors: Joormann, Imke; Orlin, James B.; Pfetsch, Marc E.
• Is Part Of: Networks. Volume 68:Issue 2(2016)
• Page Start: 121
• Page End: 129
• Publication Date: 2016-06-28
• Subjects: flow network -- irreducible infeasible subsystem -- Gale‐Hoffman theorem -- infeasibility analysis -- witness -- max flow–min cut -- NP‐hardness; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21686
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : 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 N P ‐hard. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 121–129 2016