Efficient reversal of transductions of sparse graph classes

Résumé Technique : Inversion Efficace des Transductions de Classes de Graphes Creux

Énoncé du Problème
L'article traite du défi algorithmique de l'« inversion » des transductions de premier ordre sur des classes de graphes creux. Une transduction de premier ordre est une opération générale qui transforme un graphe $H$ en un graphe $G$ via la copie de sommets, leur marquage avec des couleurs, et la définition de nouvelles adjacences à l'aide de formules de logique du premier ordre. Bien qu'il soit établi qu'un graphe $H$ appartenant à une classe creuse bien structurée (par exemple, à expansion bornée) produit un graphe $G$ qui conserve des propriétés structurelles utiles, le problème inverse reste difficile : étant donné un graphe $G$ issu d'une classe $\mathcal{C}$ connue pour être transductible à partir d'une classe creuse $\mathcal{D}$, peut-on calculer efficacement une représentation « creuse » $H \in \mathcal{D}$ telle que $G$ puisse être récupéré de $H$ via une interprétation de premier ordre ?

Des travaux antérieurs avaient établi des procédures de sparsification en temps polynomial pour des sous-classes spécifiques, telles que celles ayant un degré structurellement borné, une largeur de chemin (pathwidth) ou une largeur d'arbre (treewidth) bornées. Cependant, pour la classe plus large de graphes à expansion structurellement bornée (ceux transductibles à partir de classes à expansion bornée), aucune procédure de sparsification efficace respectant le modèle standard n'était connue. Les méthodes existantes pour cette classe étaient soit peu efficaces, soit, dans le cas de travaux récents sur les classes monadiquement stables, produisaient des sorties qui n'étaient que « presque partout non denses », échouant ainsi à garantir les bornes constantes sur les paramètres structurels (comme les nombres de coloration faible) nécessaires à des applications algorithmiques robustes.

Méthodologie
Les auteurs proposent un nouveau cadre algorithmique qui construit une représentation creuse $H$ pour tout graphe d'entrée $G$ issu d'une classe monadiquement stable possédant une complexité de voisinage intrinsèquement linéaire. La méthodologie repose sur trois composantes techniques centrales :

1. Réduction Bipartite : L'algorithme transforme d'abord le graphe d'entrée $G$ en un graphe biparti $G'$ sans perte de généralité, permettant aux étapes suivantes d'opérer dans un cadre bipartite.
2. Branchement Itératif via les Quasi-Jumeaux (Near-Twins) : La contribution technique centrale est un nouveau lemme (Lemme 12) qui calcule efficacement un « branchement » d'un graphe biparti. Cela implique de partitionner un côté de la bipartition en ensembles $P_i$, chacun étant dominé par un sommet « leader » spécifique $\ell_i$ de l'autre côté. Crucialement, chaque sommet du côté non dominé possède des voisins dans au plus un nombre constant $k^*$ de ces ensembles. Ceci est réalisé en identifiant de manière itérative des $k$-quasi-jumeaux (sommets ayant des voisinages presque identiques) en utilisant le lemme de compactage de Haussler et une propriété de transitivité des quasi-jumeaux dans les graphes exempts de demi-graphes (half-graph-free).
3. Construction d'Arbre (Sparsification) : En utilisant le lemme de branchement, l'algorithme construit de manière récursive un arbre enraciné $T$. À chaque nœud $p$ de l'arbre, l'algorithme associe un sous-graphe $G(p)$ (soit un sous-graphe induit du graphe actuel, soit son complément bipartite). L'algorithme calcule un branchement gauche ou droit de $G(p)$, crée des enfants dans l'arbre pour chaque branche, et assigne le complément bipartite de la branche au nœud enfant. Ce processus alterne entre sous-graphes induits et compléments, réduisant ainsi efficacement l'indice de l'échelle (la taille du plus grand demi-graphe induit) à chaque deux étapes. Puisque la classe d'entrée est monadiquement stable, l'indice de l'échelle est borné, garantissant que l'arbre $T$ a une hauteur bornée.

Le graphe de sortie final $H$ est constitué des sommets du graphe original $G$ (sans arêtes internes) connectés aux nœuds de l'arbre $T$. Un sommet $v \in V(G)$ est connecté à un nœud $p \in T$ si $v$ appartient au sous-graphe associé à $p$.

Contributions Principales et Résultats
L'article établit le résultat principal suivant (Théorème 1) :

• Théorème Principal : Pour toute classe de graphes $\mathcal{C}$ qui est monadiquement stable et possède une complexité de voisinage intrinsèquement linéaire, il existe un algorithme s'exécutant en $O(n^4)$ qui, étant donné un graphe $G \in \mathcal{C}$, calcule un graphe coloré $H$ appartenant à une classe $\mathcal{D}$ d'expansion bornée tel que $G$ puisse être récupéré de $H$ via une interprétation de premier ordre fixée.
• Caractérisation de l'Expansion Structurellement Bornée : Les auteurs prouvent que les conditions d'être monadiquement stable et d'avoir une complexité de voisinage intrinsèquement linéaire sont équivalentes à avoir une expansion structurellement bornée. Cela résout une question ouverte concernant la caractérisation structurelle de ces classes.
• Corollaire sur la Largeur de Fusion (Merge-Width) : L'article relie également ces propriétés à la « largeur de fusion », montant qu'une classe possède une expansion structurellement bornée si et seulement si elle est monadiquement stable et possède une largeur de fusion bornée.
• Implications Algorithmiques : Le prétraitement en $O(n^4)$ permet de réduire le problème de vérification de modèle (model-checking) du premier ordre (FO) sur n'importe quelle classe d'expansion structurellement bornée vers le cadre des classes à expansion bornée. Cela permet le transfert de résultats algorithmiques avancés connus pour l'expansion bornée (tels que l'énumération à délai constant, le comptage de solutions et les structures de données dynamiques pour les requêtes FO) vers la classe plus large des graphes à expansion structurellement bornée.
• Préservation des Propriétés : La classe sparsifiée $\mathcal{D}$ hérite des propriétés fermées sous transduction. Par exemple, si $\mathcal{C}$ a une largeur de cliché linéaire (linear cliquewidth) bornée, la classe $\mathcal{D}$ résultante aura une largeur de chemin (pathwidth) bornée ; si $\mathcal{C}$ a une largeur de jumeau (twin-width) bornée, $\mathcal{D}$ aura une largeur de jumeau creuse (sparse twin-width) bornée.

Signification
L'article affirme répondre à un problème ouvert majeur soulevé par Gajarský et al. [17] concernant l'existence de procédures de sparsification efficaces pour les classes d'expansion structurellement bornée. Contraques aux approches précédentes qui produisaient des garanties structurelles plus faibles (bornes sous-polynomiales) ou étaient limitées à des sous-classes plus étroites, ce travail fournit une procédure qui garantit que la sortie appartient à une classe d'expansion bornée. Cette distinction est cruciale car les classes d'expansion bornée admettent l'élimination du quantificateur et d'autres outils algorithmiques puissants qui ne sont pas actuellement disponibles pour les classes monadiquement stables générales.

Les auteurs soulignent que leur méthode est auto-contenue et repose sur une application directe de leur lemme principal (Lemme 12) combinée à des arguments de base sur les demi-graphes, évitant ainsi la machinerie complexe du « Flipper game » utilisée dans les travaux précédents. Le résultat unifie la théorie structurelle des graphes creux avec l'efficacité algorithmique, démontant que les propriétés structurelles des classes monadiquement stables avec une complexité de voisinage linéaire sont suffisantes pour garantir une sparsification efficace vers l'expansion bornée.