Analyse probabiliste du problème de génération de l'hypergraphe transverse

Le calcul des traverses minimales d’un hypergraphe, appelé problème de génération d’hypergraphes transversaux (THG), est un problème majeur en informatique théorique, dont la complexité reste ouverte. Cette thèse étudie la complexité en moyenne de l’algorithme classique de Berge, l’une des méthodes les plus anciennes.Nous considérons deux modèles d’hypergraphes aléatoires : le modèle d’Erdős–Rényi et un modèle multiparamétrique. Par des outils de combinatoire analytique, nous obtenons des estimations asymptotiques de la probabilité qu’un ensemble soit un transversal minimal dans le modèle multiparamétrique. Pour le modèle d’Erdős–Rényi, nous calculons le nombre moyen de transversaux minimaux, puis nous démontrons que la complexité en moyenne de l’algorithme de Berge est quasi-linéaire en ce nombre moyen.Enfin, nous comparons Berge à MTMiner, Dong–Li et RS. En moyenne, Berge surpasse MTMiner, et sa complexité en moyenne fournit aussi une borne supérieure pour Dong–Li et RS, renforçant ainsi la portée de notre analyse.