Acyclicité des hypergraphes et complexité

Plusieurs notions non-équivalentes généralisent l’acyclicité des graphes aux hypergraphes : la Berge-acyclicité, la gamma-acyclicité, la beta-acyclicité et l’alpha-acyclicité. Elles sont issues principalement de la théorie des bases de données mais sont étudiées dans d’autres domaines comme la combinatoire et la logique. On présente chacune de ces notions en insistant sur leur complexité. On regarde plus en détail la complexité des problèmes de décision suivants : l’existence d’un sous-hypergraphe acyclique couvrant et d’un sous- hypergraphe acyclique ayant un nombre donné d’hyperarêtes. La complexité de ces problèmes dépend du type d’acyclicité considéré et de la taille des hyperarêtes.