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.