Minimal Representation of Directed Hypergraphs

Abstract

In this paper the problem of minimal representations for particular classes of directed hypergraphs is analyzed. Various concepts of minimal representations of directed hypergraphs (called minimal equivalent hypergraphs) are introduced as extensions to the concepts of transitive reduction and minimum equivalent graph of directed graphs. In particular, we consider equivalent hypergraphs which are minimal with respect to all parameters which may be adopted to characterize a given hypergraph (number of hyperarcs, number of adjacency lists required for the representation, length of the overall description,etc.). The relationships among the various concepts of minimality are discussed and their computational properties are analyzed. In order to derive such results, a graph representation of hypergraphs is introduced.