Optimization Online


Complexity of Minimum Irreducible Infeasible Subsystem Covers for Flow Networks

Imke Joormann(joormann***at***opt.tu-darmstadt.de)
Marc E. Pfetsch(pfetsch***at***opt.tu-darmstadt.de)

Abstract: 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.

Keywords: flow network, minIISCover

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Other )


Download: [PDF]

Entry Submitted: 03/07/2015
Entry Accepted: 03/07/2015
Entry Last Modified: 03/07/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society