• search hit 2 of 9
Back to Result List

Complexity of Minimum Irreducible Infeasible Subsystem Covers for Flow Networks

Submission Status:accepted for publication
  • For an infeasible network flow system with supplies and demands, we consider the problem of finding a minimum irreducible infeasible subsystem cover, i.e., a smallest set of constraints that must be dropped to obtain a feasible system. The special cases of covers which only contain flow balance constraints (node cover) or only flow bounds (arc cover) are investigated as well. We show strong NP-hardness of all three variants. Furthermore, we show that finding minimum arc covers for assignment problems is still hard and as hard to approximate as the set covering problem. However, the minimum arc cover problem is polynomially solvable for networks on cactus graphs. This leads to the development of two different fixed parameter algorithms with respect to the number of elementary cycles connected at arcs and the treewidth, respectively. The latter can be adapted for node covers and the general case.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Imke Joormann, Marc E. Pfetsch
DOI:https://doi.org/10.1016/j.dam.2018.02.025
Parent Title (English):Discrete Applied Mathematics
Document Type:Article
Language:English
Date of Publication (online):2018/02/19
Release Date:2021/10/05
Volume:244
First Page:124
Last Page:142
Institutes:Technische Universität Darmstadt
Subprojects:A01
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International