Groupe d’études et de recherche en analyse des décisions




A hypergraph H=(X,E) is nested if its edges are pairwise disjoint or included one into the other. The nesticity of H is defined as the smallest number of nested partial hypergraphs into which H can be partitioned. Determining the nesticity of H reduces to graph coloring. Hypergraphs of nesticity 2 are shown to be unimodular. A prehypergraph H' is obtained from a hypergraph H by specifying that some or all vertices from a given subset of each edge may be deleted. H' is thus a set of hypergraphs, called its realizations. Determining the nesticity of a prehypergraph H', i.e., the smallest nesticity of its realizations, reduces to satisfiability.

, 14 pages

Ce cahier a été révisé en mai 1997