Résumé - Paramétrisations de la Largeur Hypertree Fractale et Généralisée en FPT

Paramétrisations de la Largeur Hypertree Fractale et Généralisée en FPT

2025-07-15 08:23:01

{"Matthias Lanzinger","Igor Razgon","Daniel Unterberger"}

{cs.DS,cs.CC}

Ce document présente les premiers algorithmes tractables en paramètres fixes (FPT) pour déterminer précisément plusieurs paramètres centraux de décomposition des hypergraphes, y compris la largeur hypertree généralisée (ghw) et la largeur hypertree fractionnaire (fhw). Malgré leur importance reconnue en théorie de la complexité, dans les bases de données et dans la satisfaction de contraintes, aucun algorithme exact FPT pour ces paramètres n'était connu précédemment. Les auteurs obtiennent leurs résultats pour les classes d'hypergraphes avec un rang et un degré bornés. Leur approche étend un algorithme récent pour la largeur en arbre (Bojańcyk et Pilipczuk, LMCS 2022) utilisant des transductions de second ordre monadique (MSO). Ce cadre leur permet de surmonter les obstacles techniques significatifs présentés par les hypergraphes, dont les décompositions structurelles sont plus complexes que celles de leurs homologues graphiques. Les contributions principales du document sont les suivantes : 1. **Définition de fonctions de largeur gérables** : Les auteurs définissent une nouvelle classe de fonctions de largeur, appelées gérables, qui sont plus générales que les fonctions de largeur traditionnelles utilisées pour la largeur en arbre. Cela leur permet d'appliquer leurs algorithmes à une plus large gamme de mesures de largeur d'hypergraphes. 2. **Généralisation de l'algorithme pour la largeur en arbre** : Les auteurs étendent l'algorithme pour la largeur en arbre de Bojańczyk et Pilipczuk à un cadre général pour les paramètres d'hypergraphes. Cela leur permet d'appliquer l'algorithme à la ghw et à la fhw. 3. **Construction de transductions** : Les auteurs construisent des transductions MSO qui lient les décompositions en arbres aux forêts d'élimination optimaux. Cela leur permet de vérifier la largeur f d'un hypergraphe. 4. **Algorithme pour vérifier la ghw et la fhw** : Les auteurs présentent un algorithme FPT pour vérifier la ghw et la fhw pour les hypergraphes avec un rang et un degré bornés. Les auteurs croient que leurs résultats auront des implications significatives pour l'étude des hypergraphes et leurs applications dans divers domaines. Ils discutent également de plusieurs problèmes ouverts liés à leur travail, y compris la possibilité de supprimer la contrainte de degré de leurs algorithmes.