Algorithmes d'espace de journalisation sur les graphiques avec une largeur d'arbre bornée

La largeur de l'arbre mesure la proximité d'un graphique avec un arbre. Il est difficile de calculer la largeur de l'arbre NP. L' algorithme d' approximation le plus connu atteint le facteur . $O(\sqrt{{\log}n})$

Le théorème de Courcelle stipule que toute propriété de graphes définissables en logique monadique du second ordre (MSO2) peut être décidée en temps linéaire sur n'importe quelle classe de graphes de largeur d'arbre borné . Un article récent a montré que le théorème de Courcelle tient toujours lorsque le «temps linéaire» est remplacé par «espace de journal». Cependant, cela ne règle pas la complexité spatiale de l' isomorphisme de graphes sur des graphes avec une largeur d'arbre bornée. Le résultat le plus connu le place dans LogCFL.

Y a-t-il d'autres problèmes qui sont:

NP-hard (ou non connu en P) sur les graphiques généraux, et
connu pour être résoluble en temps linéaire / polynomial sur des graphiques avec une largeur d'arbre bornée, et
PAS connu pour être dans LogSpace?

cc.complexity-theory ds.algorithms graph-theory space-bounded treewidth Shiva Kintali
la source

Quel est le

mentionné dans le facteur d'approximation?

n

$n$

gphilip

est le nombre de sommets dans le graphe d'entrée.

n

$n$

Shiva Kintali

On peut, en général, faire mieux que

en approximant la largeur d'arbre. Le meilleur algorithme d'approximation du temps polynomial que je connaisse atteint un

O (\sqrt{\log n})

$O(\sqrt{\log n})$

facteur d'approximation, où

est la largeur d'arbre du graphique. Voir Feige, Hajiaghayi et Lee,Algorithmes d'approximation améliorés pour les séparateurs de sommets de poids minimum, STOC 2005.

O (\sqrt{\log w})

$O(\sqrt{\log w})$

w

$w$

gphilip

Réponses:

Le polynôme de Tutte en est un exemple.

Il s'agit d'une généralisation du polynôme chromatique , qui lui-même est un problème # P-difficile dans toute formulation raisonnable. Dans

Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width , SD Noble, Combinatorics, Probability and Computing, 1998,

un algorithme polynomial de temps est donné où la complexité temporelle est d'environ , où est la largeur d'arbre et est le nombre de nœuds. Des travaux connexes peuvent être vus ici . Pour une enquête, il y a un article sur Arxiv , où le problème de complexité discuté dans la section 8. $O(f(k)n^{4+\epsilon})$ $k$ $n$

Il semble que le problème ne puisse pas être exprimé directement dans MSO2, même si je ne connais pas les définitions détaillées ... J'espère que ce problème est ce dont vous avez besoin!

Hsien-Chih Chang 張顯之
la source

Quelle est la fonction f?

Michael Blondin

Selon l'article, c'est une fonction en

avec un ordre d'environ

k

$k$

O (2^{(k^{3 + ϵ})})

$O(2^{(k^{3+\epsilon})})$

Hsien-Chih Chang 張顯之

Makowski dit que «tous les polynômes graphiques étudiés dans la littérature sont définissables par SOL», et donne une formulation du polynôme Tutte en termes de SOL, page 15 de «Du zoo à la zoologie: vers une théorie générale des polynômes graphiques». Dans «Utilisations algorithmiques du théorème de Feferman-Vaught», il étend le théorème de Courcelle pour montrer la tractabilité des polynômes définissables par SOL sur des graphiques de largeur d'arbre bornés.

Yaroslav Bulatov