Avantages algorithmiques de la largeur de chemin sur la largeur d'arbre

La largeur d'arbre joue un rôle important dans les algorithmes FPT, en partie parce que de nombreux problèmes sont paramétrés FPT par la largeur d'arbre. Une notion connexe, plus restreinte, est celle de largeur de chemin. Si un graphe a une largeur de chemin , il a également une largeur d'arbre au plus , tandis que dans le sens inverse, la largeur d'arbre implique uniquement une largeur de chemin au plus et cela est serré. $k$ $k$ $k$ $k\log n$

Compte tenu de ce qui précède, on peut s'attendre à ce qu'il puisse y avoir un avantage algorithmique significatif pour les graphiques de largeur de chemin bornée. Cependant, il semble que la plupart des problèmes qui sont FPT pour un paramètre sont FPT pour l'autre. Je suis curieux de connaître des contre-exemples à cela, c'est-à-dire des problèmes qui sont "faciles" pour la largeur de chemin mais "difficiles" pour la largeur d'arbre.

Permettez-moi de mentionner que j'ai été motivé à poser cette question en rencontrant un article récent d'Igor Razgon ("Sur les OBDD pour les CNF de largeur d'arbre bornée", KR'14) qui a donné un exemple d'un problème avec une solution à lorsque est la largeur de chemin et une limite inférieure (approximativement) lorsque est la largeur d'arbre. Je me demande s'il existe d'autres spécimens avec ce comportement. $2^{k}n$ $k$ $n^k$ $k$

Résumé: Existe-t-il des exemples de problèmes naturels qui sont paramétrés W-hard par la largeur d'arbre mais FPT paramétrés par la largeur de chemin? Plus largement, existe-t-il des exemples de problèmes dont la complexité est connue / supposée être bien meilleure lorsqu'elle est paramétrée par la largeur de chemin plutôt que par la largeur d'arbre?

parameterized-complexity treewidth graph-minor Michael Lampis
la source

Il y a des problèmes qui sont faciles sur les chemins mais NP-durs sur les arbres. Celles-ci incluent le multitouche minimal et le multiflux entier maximal.

Chandra Chekuri

@ChandraChekuri C'est un bon point, mais les algorithmes pour les chemins pour de tels problèmes se généralisent-ils généralement à la largeur de chemin? Par exemple, pour le multiflow entier max, je pense que ce n'est pas le cas. Garg, Vazirani et Yannakakis ont prouvé la dureté NP pour les arbres dans "Algorithmes d'approximation primal-dual pour l'écoulement intégral et la coupe multiple dans les arbres". La réduction utilise un arbre de hauteur 3. Cela signifie que le problème est NP-difficile pour une largeur de chemin constante.

Michael Lampis

Ce n'est encore une fois pas une réponse claire à la question d'origine. On sait que l'écart d'écoulement dans les graphiques de largeur de trajet k est limité par f (k) pour une fonction f via un résultat de Lee et Sidiropoulos. Il est important de savoir si un tel résultat est valable pour la largeur d'arbre. Le cas k = 3 est ouvert pour la largeur d'arbre.

Chandra Chekuri

Le meilleur algorithme pour le cycle hamiltonien paramétré par la largeur de chemin a le temps d'exécution

(arxiv.org/abs/1211.1506) alors que la meilleure arborescence est de

(arxiv.org/abs/1103.0534) Ce n'est probablement qu'un écart qui doit être fermé, cependant.

(2 + \sqrt{2})^{p w}

$(2+\sqrt{2})^{pw}$

4^{t w}

$4^{tw}$

daniello

On montre que [1] le problème du facteur chinois mixte (MCPP) paramétré par la largeur de chemin est -difficile, même si tous les bords et arcs du graphe d'entrée ont le poids et sont FPT par rapport à la profondeur des arbres. C'est le premier problème dont on sait qu'il a été démontré qu'il est -difficile en ce qui concerne la largeur d'arbre mais FPT en ce qui concerne la profondeur d'arbre. Notez que la largeur de chemin d'un graphe se situe entre sa largeur d'arbre et sa profondeur d'arbre. $W[1]$ $G$ $1$ $W[1]$

Le problème Steiner Multicut, qui demande, étant donné un graphe non orienté , une collection , , d'ensembles terminaux de taille au plus , et un entier , qu'il y ait un ensemble d'au plus bords ou nœuds tel que de chaque ensemble au moins un paire de bornes se trouve dans différentes composantes connexes de . $G$ $T = \{T_1, . . . , T_t\}$ $T_i ⊆ V(G)$ $p$ $k$ $S$ $k$ $T_i$ $G \ S$

$W[1]$ $k$ $p = 3$ $tw(G) = 2$

[1] https://core.ac.uk/download/pdf/77298274.pdf

[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf

Rupei Xu
la source

Avantages algorithmiques de la largeur de chemin sur la largeur d'arbre

Réponses: