La largeur d'arbre (treewidth) du graphe d'incidence d'une formule logique ou d'une instance CNF : le graphe d'incidence possède un sommet pour chaque variable et chaque clause, et des arêtes entre une variable et chaque clause qui la contient ; le treewidth d'incidence mesure à quel point cette structure bipartite est proche d'un arbre.

Principe

Un faible treewidth d'incidence traduit une parcimonie structurelle et une interdépendance limitée entre clauses et variables, permettant des algorithmes de programmation dynamique ou des algorithmes paramétrés qui exploitent la décomposition en arbre.

Démonstration

Une CNF dont le graphe d'incidence a un treewidth borné admet des algorithmes SAT en temps linéaire en la taille de la formule mais exponentiel en le treewidth ; de nombreux algorithmes pour la satisfaction de contraintes et le comptage de modèles exploitent un small treewidth d'incidence pour obtenir de la tractabilité.

Mauvaise application

Confondre le treewidth d'incidence avec le treewidth primal (qui relie les variables apparaissant ensemble) ou le treewidth dual (interactions clause-clause) conduit à de fausses conclusions sur l'applicabilité algorithmique, car ces paramètres diffèrent et gouvernent des comportements algorithmiques distincts.

Conséquence

Un treewidth d'incidence borné implique l'existence de décompositions structurées qui rendent des problèmes autrement difficiles fixés-paramétrables (FPT) en ce paramètre, et oriente les choix d'encodage pour réduire les interactions.

Inversion

On peut inverser la perspective structurelle et considérer des mesures de localité telles que la taille des clauses ou le degré des variables ; un treewidth d'incidence élevé n'exclut pas des fragments localement tractables mais indique un couplage global qui rend inefficace une simple décomposition.

Limite

Dépend de la construction du graphe d'incidence (variables et clauses comme sommets, arêtes pour l'incidence) ; exclut les simplifications sémantiques comme l'élimination de variables ou la subsomption sauf si elles sont appliquées avant la construction du graphe, et diffère d'autres paramètres graphiques par les types de sommets et la définition des arêtes.

Tension sémantique

Est en tension avec le treewidth primal et dual : le treewidth primal peut être faible tandis que le treewidth d'incidence est élevé et réciproquement ; le choix du modèle de graphe influe sur les garanties algorithmiques disponibles.

Synthèse

Le treewidth d'incidence est un paramètre structural du graphe bipartite variable-clause qui quantifie le couplage global ; des valeurs faibles permettent des techniques de programmation dynamique et FPT pour SAT et CSP, et sa relation aux autres mesures de largeur guide les décompositions et encodages efficaces.