Théorème de Courcelle

En algorithmique et en théorie de la complexité, le théorème de Courcelle est le suivant : Modèle:Théorème

C'est un métathéorème, dans le sens où il concerne une classe de problèmes algorithmiques. Le théorème est dû à Bruno CourcelleModèle:Refm. Dans le contexte de ce théorème, un graphe est donné par un ensemble de sommets $S$ et une relation d'adjacence $\mathrm{a}\mathrm{d}\mathrm{j}$, et la restriction à la logique monadique signifie que la propriété étudiée peut contenir des quantificateurs sur des ensembles de sommets (quantificateurs du second ordre sur des prédicats monadiques), mais pas de quantificateurs sur des ensembles d'arcs (ces quantificateurs du second ordre porteraient sur des prédicats binaires).

Exemple

La propriété, pour un graphe, d'être colorable en trois couleurs, s'exprime par l'existence de trois ensembles de sommets $R,V,B$ que l'on peut définir par la formule monadique du second ordre suivante

$\begin{array}{cc}\mathrm{\exists }R,V,B& (\mathrm{\forall }s(s\in R\vee s\in V\vee s\in B))\wedge \\ & (\mathrm{\forall }s,t((s\in R\wedge t\in R)\vee (s\in V\wedge t\in V)\vee (s\in B\wedge t\in B))\to \mathrm{\neg }\mathrm{a}\mathrm{d}\mathrm{j}(s,t)).\end{array}$

La première partie de la formule assure que les trois ensembles couvrent tous les sommets (tout sommet a une couleur) et la deuxième partie exprime que ces trois ensembles forment un ensemble indépendant. Ainsi, le théorème de Courcelle dit que la 3-coloriabilité d'un graphe en la largeur d'arborescence bornée peut être testée en temps linéaire.

Une des approches de preuve du théorème de Courcelle utilise la construction d'un automate d'arbres ascendant qui réalise la décomposition arborescente du graphe pour le reconnaitre.

Article connexe

• Théorème de Robertson-Seymour