Rendre une décomposition d'arbre de largeur minimale maigre en temps polynomial

Comme on le sait, une décomposition arborescente d'un graphe est constituée d'un arbre avec un sac associé pour chaque sommet , ce qui satisfait les conditions suivantes: $G$ $T$ $T_v \subseteq V(G)$ $v \in V(T)$

Chaque sommet du se produit dans un certain sac de . $G$ $T$
Pour chaque bord de il y a un sac contenant les deux extrémités du bord. $G$
Pour chaque sommet , les sacs contenant induisent un sous - arbre associé de . $v \in V(G)$ $v$ $T$

Nous pouvons également exiger la condition suivante, appelée maigreur , de notre décomposition:

Pour chaque paire de sacs , de , si et avec , alors soit a) il y a chemins sommet-disjoints dans , ou b) l'arbre contient une arête sur le chemin du nœud au nœud telle que et l'ensemble intersecte tous chemins dans . $T_a$ $T_b$ $T$ $A \subseteq T_a$ $B \subseteq T_b$ $|A| = |B| = k$ $k$ $A-B$ $G$ $T$ $pq$ $a$ $b$ $|V(T_p) \cap V(T_q)| \leq k$ $V(T_p) \cap V(T_q)$ $A-B$ $G$

Robin Thomas a montré qu'il y a toujours une décomposition d'arbre de largeur minimale qui est également pauvre, et des preuves plus simples de ce fait ont été fournies par plusieurs auteurs, par exemple par Patrick Bellenbaum & Reinhard Diestel .

Ce qui m'intéresse est le suivant: étant donné un graphe et une décomposition arborescente de largeur minimale de , pouvons-nous trouver une décomposition arborescente maigre de largeur minimale de en temps polynomial? $G$ $G$ $G$

Les deux preuves mentionnées ne donnent pas une constructivité aussi efficace. Dans l'article de Bellenbaum et Diestel, il est mentionné qu'une "autre preuve (plus constructive) du théorème de Thomas a été donnée dans P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000." Hélas, je n'ai pas pu trouver le manuscrit en ligne et mon allemand n'est pas terrible.

ds.algorithms graph-theory graph-algorithms treewidth Bart Jansen
la source

Bonne question. Trouver une décomposition d'arbre de largeur minimale est NP-difficile, donc votre problème est quelque peu mal posé (il apparaît). Je suppose que l'on peut demander ceci pour un cas de largeur d'arbre borné ou dans le sens d'approximation.

Chandra Chekuri

Mais dans son cas, il a reçu une décomposition d'arbre de largeur minimale et il veut un algorithme pour le rendre plus léger.

Suresh Venkat

@SureshVenkat: Je me rends compte qu'on lui donne une décomposition d'arbre de largeur minimale mais comment pouvez-vous même vérifier qu'elle est correcte? De plus, une décomposition d'arbre allégée s'adapte localement à la largeur d'arbre des différentes parties du graphique, donc avoir une décomposition d'arbre du graphique global qui est optimale n'évite pas le problème de trouver la largeur d'arbre des morceaux locaux qui est difficile.

Chandra Chekuri

Les décompositions d'arbres lisses (où tous les sacs ont la même taille et deux sacs adjacents diffèrent par exactement un sommet) sont beaucoup plus faciles à manipuler que les décompositions d'arbres générales, et il est facile de voir qu'il y a toujours une décomposition d'arbre de largeur minimale qui est lisse . Vous pouvez donc peut-être obtenir une construction efficace en restreignant l'une des constructions connues à celles-ci. Existe-t-il toujours une décomposition d'arbre de largeur minimale qui soit lisse et maigre?

Diego de Estrada,

@ChandraChekuri Je suppose que le problème de vérification disparaît si vous le dites comme un problème de promesse, mais je vois votre point sur la décomposition d'un arbre qui ne vous donne pas nécessairement suffisamment d'informations pour vous adapter. Mais la question suivante pourrait être plausible: existe-t-il un moyen de modifier "localement" une décomposition d'arbre donnée pour la rendre "légère" sans augmenter la largeur d'arbre?

Suresh Venkat

Voici une raison formelle pour laquelle le problème n'est pas résolu poly-temps à moins que P = NP. Nous savons que trouver la largeur d'arbre d'un graphe donné est NP-difficile. Étant donné un graphe nous pouvons ajouter une clique disjointe de taille pour créer un nouveau graphe . Un arbre décomposition min-largeur de peut être obtenu de la manière suivante: il comporte deux noeuds avec une poche contenant tous les noeuds de la clique et l'autre contenant tous les nœuds de . Maintenant , ce qui en fait maigre arbre de décomposition , il faudrait trouver une décomposition appentis arbre du graphe original qui serait, en tant que sous-produit, donner la largeur arborescente de . $G$ $V(G)+1$ $G'$ $G'$ $G$ $G$ $G$

Chandra Chekuri
la source

Bon point. Savez-vous si l'on sait quelque chose sur les algorithmes de temps paramétrés et / ou modérément exponentiels pour trouver des décompositions d'arbre maigre?

Bart Jansen

Rendre une décomposition d'arbre de largeur minimale maigre en temps polynomial

Réponses: