Aspects paramétrés de la Dualisation – PARADUAL

La dualisation des hypergraphes est sans nul doute l’un des problèmes ouverts les plus importants en énumération, apparaissant au carrefour de nombreux domaines de l’informatique allant de la logique aux bases de données. Le problème, noté Trans-Enum, vise à lister tous les transversaux minimaux d’un hypergraphe donné. Comme le nombre de solutions peut être exponentiel en la taille de l’entrée, l’objectif est d’obtenir un algorithme dit output-polynomial, i.e., fonctionnant en temps polynomial en les tailles de l’entrée plus de la sortie. À ce jour, le meilleur algorithme connu s’exécute en temps output quasi-polynomial. L’existence d’un algorithme output-polynomial pour Trans-Enum est une question fascinante et scientifiquement stimulante. En outre, un certain nombre de paramètres permettant d’approcher cette question ont été identifiés. Parmi eux, la dégénérescence, la dimension ou encore la taille d’une clique maximum, ce dernier paramètre étant issu du contexte équivalent de la domination dans les graphes. Chacun de ces cas donne un algorithme pour Trans-Enum avec un temps d’exécution N^f(k), où f est une fonction calculable, N est la somme des tailles de l’entrée et de la sortie, et k est le paramètre. Bien que de complexité output-polynomiale à paramètre fixé, ces algorithmes sont cependant inutilisables en pratique, même lorsque le paramètre considéré est relativement petit. Pour les cas pratiques, des temps d’exécution de la forme f(k)*poly(N) sont bien plus souhaitables. Ceux-ci sont dits FPT et suggèrent une meilleure applicabilité des problèmes. L’objectif principal de la complexité paramétrée est d’identifier les problèmes et paramètres qui admettent de tels temps d’exécution. Dans ce sens, de nombreuses nombreuses techniques ont vu le jours ces 20 dernières années permettant un progrès important sur de nombreux problèmes. Pour certains paramètres, en revanche, de tels temps d’exécutions ne peuvent être obtenu sous des hypothèses classiques de complexité. Dans cette direction, la complexité paramétrée offre également un grand nombre d’outils permettant de prouver ces bornes inférieures. Dans le projet PARADUAL, nous proposons d’étudier la dualisation des hypergraphes et de problèmes liés à travers le prisme de la complexité paramétrée. Avec cette approche, plutôt nouvelle en énumération algorithmique, nous cherchons à obtenir de nouveaux algorithmes efficaces pour la dualisation, ou à identifier les paramètres qui la rendent difficile en prouvant des bornes inférieures, lesquelles manquent cruellement en énumération à ce jour.