Finding hypernetworks in directed hypergraphs

•Theoretical and computational relevance of hypernetworks.•Relations to other concepts, namely, flow hypergraphs and dominators.•A simple and fast method for finding the s-hypernetwork.•Linear time methods for s-hypernetworks in acyclic hypergraphs and directed graphs.•A linear time method for the (s, d)-hypernetwork in acyclic hypergraphs.

The term “hypernetwork” (more precisely, s-hypernetwork and (s, d)-hypernetwork) has been recently adopted to denote some logical structures contained in a directed hypergraph. A hypernetwork identifies the core of a hypergraph model, obtained by filtering off redundant components. Therefore, finding hypernetworks has a notable relevance both from a theoretical and from a computational point of view.In this paper we provide a simple and fast algorithm for finding s-hypernetworks, which substantially improves on a method previously proposed in the literature. We also point out two linearly solvable particular cases.Finding an (s, d)-hypernetwork is known to be a hard problem, and only one polynomially solvable class has been found so far. Here we point out that this particular case is solvable in linear time.