qu'est-ce qui est facile pour les graphiques exclus mineurs?

Le nombre approximatif de colorations semble être facile sur les graphiques mineurs exclus utilisant l' algorithme de Jung / Shah. Quels sont les autres exemples de problèmes difficiles sur les graphiques généraux mais faciles sur les graphiques mineurs?

Mise à jour 10/24 Il semble suivre les résultats de Grohe que la formule qui est FPT pour tester sur les graphiques à largeur d'arbre bornée est FPT pour tester sur les graphiques exclus mineurs. Maintenant, la question est - comment est-elle liée à la facilité de comptage des affectations satisfaisantes d'une telle formule?

La déclaration ci-dessus est fausse. MSOL est FPT sur les graphiques de largeur d'arbre bornée, mais la colorabilité 3 est NP-complète sur les graphiques plans qui sont mineurs exclus.

Le résultat le plus général connu est celui de Grohe. Un résumé a été présenté en juillet 2010:

• Martin Grohe, Définissabilité à virgule fixe et temps polynomial sur les graphiques avec mineurs exclus , LICS 2010. ( PDF )

En bref, toute instruction exprimable en logique à virgule fixe avec comptage possède un algorithme à temps polynomial sur les classes de graphiques avec au moins un mineur exclu. (FP + C est une logique de premier ordre augmentée d'un opérateur à virgule fixe et d'un prédicat qui donne la cardinalité d'ensembles de sommets définissables). L'idée clé est que l'exclusion d'un mineur permet aux graphiques de la classe d'avoir ordonné des décompositions en treillis définissables en logique à virgule fixe (sans compter).

Ainsi, une grande classe de réponses à votre question peut être obtenue en considérant les propriétés définissables dans FP + C mais difficiles à compter.

Edit: je ne suis pas sûr que cela réponde réellement à votre question, encore moins pour votre mise à jour. Le pointeur et la déclaration du résultat de Grohe sont corrects, mais je ne pense pas que le texte supprimé soit pertinent pour votre question. (Merci à Stephan Kreutzer de l'avoir signalé.) Il vaut peut-être la peine de clarifier: voulez-vous un problème de comptage difficile en général mais facile pour les classes exclues ou un problème de décision?

Une propriété intéressante des familles de graphes fermés mineurs est qu'elles ont une dégénérescence limitée . Cela signifie que tous les problèmes qui sont faciles sur les graphiques de dégénérescence limitée sont faciles sur les graphiques d'une famille fermée mineure.

Ainsi, par exemple, trouver si un graphe contient une clique de taille k est généralement un problème difficile et les meilleurs algorithmes sont comme . Cependant, si nous savons que la dégénérescence est une constante, alors les k-cliques peuvent être trouvées en temps linéaire, c'est-à-dire en temps O (n). L'article de Wikipédia sur le problème des cliques donne également quelques informations à ce sujet. (Le temps de fonctionnement précis est quelque chose comme .) Cet algorithme est de Chiba et Nishizeki .O ( k d ( G ) k n $O(n^k)$$O(k d(G)^k n)$

D'autres exemples peuvent être trouvés dans cette réponse de David Eppstein sur MathOverflow à une question similaire sur les graphiques avec dégénérescence limitée.

En complément, une autre propriété utile pour les algorithmes sur les graphes mineurs exclus est que ces graphes ont de petits séparateurs . Plus précisément, en raison de

Un algorithme de temps linéaire pour trouver un séparateur dans un graphique excluant un mineur , Bruce Reed et David R. Wood, ACM Transactions on Algorithms, 2009,

$O(n^{2/3})$$O(n^{3/2} + m)$$O(n^{1/2})$

Les séparateurs sont bons pour les techniques de programmation dynamique , et de nombreux problèmes NP-complets présentent des algorithmes rapides avec un bon rapport d'approximation, par exemple, la solution se trouve dans un facteur constant de l'optimum, ou même un PTAS. Les graphes planaires et, en général, les graphes de genre bornés sont de bons points de départ lorsque vous essayez de résoudre des problèmes sur des graphes mineurs exclus.

$O(1)$

Théorie mineure des graphes algorithmiques: décomposition, approximation et coloration par Demaine, Hajiaghayi et Kawarabayashi

Cet article donne une version algorithmique d'une certaine décomposition (quelque peu complexe à expliquer) pour les graphes mineurs exclus garantis par le théorème de Robertson et Seymour, qui donne un certain nombre de ces résultats d'approximation améliorés. Consultez également les références qui s'y trouvent.

$K_5$$K_{3,3}$

$H$$H$

$K_t$$(t-1)$$K_t$$(t-1)$$t− 2$