IIS-Hypergraphs
Jennifer K. Ryan · SIAM Journal on Discrete Mathematics · 1996
Given an inconsistent set of inequalities $Ax \leq b$, the irreducibly inconsistent subsystems (IIS’s) designate subsets of the inequalities such that at least one member of each subset must be deleted in order to achieve a feasible system. Each IIS can be considered the edge of a hypergraph. The purpose of this paper is to present several properties of this special class of hypergraphs (IIS-hypergraphs). IIS-hypergraphs are bicolourable, and their placement in Berge’s hierarchy of “hypergraphs generalizing bipartite graphs” is discussed. The greedy algorithm finds the minimum transversal for 2-uniform IIS-hypergraphs. It is shown that the greedy algorithm does not work for general IIS-hypergraphs.However, if the IIS-hypergraph is “nondegenerate” (implying uniform), the transversal number always can be found in time polynomial in the size of the hypergraph. An interesting intermediate result arises regarding blocking pairs of polyhedra arising from subspaces in $\Re^{n} $.