L'origine de la notion de largeur d'arbre

61

Ma question aujourd'hui est (comme d'habitude) un peu bête; mais je vous demanderais de bien vouloir l'examiner.

Je voulais connaître la genèse et / ou la motivation du concept de largeur d'arbre. Je comprends bien que cela soit utilisé dans les algorithmes FPT, mais je ne pense pas que ce soit la raison pour laquelle cette notion a été définie.

J'ai rédigé les notes de notes sur ce sujet dans la classe du professeur Robin Thomas . Je pense comprendre certaines des applications de ce concept (car il transfère les propriétés de séparation de l'arbre au graphe décomposé), mais pour une raison quelconque, je ne suis pas vraiment convaincu que la raison pour laquelle ce concept a été développé était de mesurer la proximité d'un graphe. à un arbre.

Je vais essayer de me rendre plus clair (je ne suis pas sûr de pouvoir le faire, merci de me faire savoir si la question n'est pas claire). J'aimerais savoir si des notions similaires existaient ailleurs dans une autre branche des mathématiques d'où cette notion était supposément "empruntée". Je suppose que ce sera la topologie - mais en raison de mon manque de formation, je ne peux rien dire.

La raison principale pour laquelle je suis curieux à ce sujet serait - la première fois que j'ai lu sa définition, je ne savais pas trop pourquoi et comment quelqu'un la concevrait et à quelle fin. Si la question n'est pas encore claire, j'essaierai finalement de l'exprimer de la manière suivante: supposons que la notion de largeur d'arbre n'existe pas. Quelles questions naturelles (ou extensions de certains théorèmes / concepts mathématiques) à des paramètres discrets amèneront-on à concevoir une définition (laissez-moi utiliser le mot impliqué) comme une largeur d'arbre.

Akash Kumar
la source
2
fyi le lien de notes de scribe obtient l’erreur 403 interdite.
vendredi

Réponses:

58

Si vous voulez vraiment savoir ce qui a conduit Neil Robertson et moi à la largeur d'arbre, ce ne sont pas du tout des algorithmes. Nous essayions de résoudre la conjecture de Wagner selon laquelle, dans tout jeu de graphes infini, l'un d'entre eux est mineur, et nous avions raison au début. Nous savions que c'était vrai si nous nous limitions à des graphiques sans chemin k-sommet; laissez-moi expliquer pourquoi. Nous savions que tous ces graphes avaient une structure simple (plus précisément, chaque graphe sans chemin k-vertex a cette structure et chaque graphe avec cette structure n'a pas de chemin 2 ^ k-vertex); et nous savions que dans chaque ensemble infini de graphes ayant tous cette structure, l'un d'eux était mineur d'un autre. La conjecture de Wagner était donc vraie pour les graphes avec une limite sur leur longueur maximale.

Nous savions également que cela était vrai pour les graphes sans étoile-k comme mineure, encore une fois parce que nous avions un théorème de structure pour de tels graphes. Nous avons essayé de rechercher des mineurs plus généraux ayant des théorèmes de structure correspondants que nous pourrions utiliser pour prouver la conjecture de Wagner, ce qui nous a conduit à la largeur du trajet; exclure N'IMPORTE QUELLE arborescence en tant que mineur et vous obtenez une largeur de chemin d'accès bornée. Si vous avez une largeur de chemin d'accès délimitée, vous pouvez ne pas avoir d'arbres mineurs. (C'était un théorème difficile pour nous; nous avions une preuve extrêmement solide dans le premier article de Graph Minors, ne le lisez pas, cela peut être rendu beaucoup plus facile.) Mais nous pourrions prouver la conjecture de Wagner pour des graphes avec une largeur de chemin bornée, et cela signifiait que c'était vrai pour les graphiques ne contenant pas d'arborescence fixe en tant que mineur; une grande généralisation du cas et des cas d'étoile que j'ai mentionnés plus tôt.

Quoi qu'il en soit, avec cela fait, nous avons essayé d'aller plus loin. Nous ne pouvions pas faire de graphiques généraux, nous avons donc pensé aux graphiques planaires. Nous avons trouvé un théorème de structure pour les graphes planaires qui ne contenait aucun graphe planaire fixe mineur (c'était facile); c'était une largeur d'arbre délimitée. Nous avons prouvé que pour tout graphe planaire fixe, tous les graphes plans qui ne le contenaient pas en tant que mineur avaient une largeur d'arbre délimitée. Comme vous pouvez l’imaginer, c’était vraiment excitant. par coïncidence, le théorème de structure pour exclure des graphes plans (à l'intérieur de plus grands graphes planaires) constituait une tournure naturelle du théorème de structure pour exclure des arbres (à l'intérieur de graphes généraux). Nous sentions que nous faisions quelque chose de bien. Et cela prouve la conjecture de Wagner pour tous les graphes plans, car nous avions ce théorème de structure.

Puisque la largeur de l'arborescence fonctionnait pour exclure les graphes plans dans les grands graphes plans, il était donc naturel de savoir si cela fonctionnait pour exclure les graphes plans dans les graphes non planaires - était-il vrai que pour chaque graphe planaire fixe, tous les graphes ne le contenant pas? mineur avait délimité la largeur des arbres? Nous n'avons pas pu le prouver pendant longtemps, mais c'est ainsi que nous avons réfléchi à la largeur des arbres des graphiques généraux. Et une fois que nous avons eu le concept de largeur d'arbre, il était assez clair que c'était bon pour les algorithmes. (Et oui, nous ne savions pas que Halin avait déjà pensé à la largeur des arbres.)

Paul Seymour
la source
18
Bienvenue sur cstheory, et merci pour cette excellente réponse!
Suresh Venkat
Merci beaucoup d'avoir pris le temps, professeur Seymour. Cette réponse regorge d’idées révélatrices et couvre la partie historique visée par la question. Donc, marquant cela comme la réponse acceptée :)
Akash Kumar
61

Voici comment vous pourriez proposer le concept de largeur d’arbre vous-même.

Supposons que vous souhaitiez compter le nombre d'ensembles indépendants dans le graphique suivant.

Les ensembles indépendants peuvent être partitionnés en ceux où le nœud supérieur est occupé et ceux où il est inoccupé

Notez maintenant que, sachant si le nœud supérieur est occupé, vous pouvez compter le nombre d'ensembles indépendants dans chaque sous-problème séparément et les multiplier. Répéter ce processus de manière récursive vous donne un algorithme pour compter des ensembles indépendants basés sur des séparateurs de graphes.

Supposons maintenant que vous n'avez plus d'arbre. Cela signifie que les séparateurs sont plus grands, mais vous pouvez utiliser la même idée. Pensez à compter des ensembles indépendants dans le graphique suivant.

Utilisez la même idée de diviser le problème en sous-problèmes sur le séparateur, vous obtenez ce qui suit

Comme dans l'exemple précédent, chaque terme de la somme se décompose en deux tâches de comptage plus petites sur le séparateur.

Notez que nous avons plus de termes dans la somme que dans l'exemple précédent car nous devons énumérer toutes les configurations de notre séparateur, ce qui peut potentiellement croître de façon exponentielle avec la taille du séparateur (taille 2 dans ce cas).

La décomposition en arborescence est une structure de données permettant de stocker de manière compacte ces étapes de partitionnement récursif. Considérez le graphique suivant et sa décomposition en arborescence

Pour compter en utilisant cette décomposition, vous devez d’abord fixer les valeurs dans les nœuds 3, 6, ce qui la divise en 2 sous-problèmes. Dans le premier sous-problème, vous corrigiez en outre le nœud 5, qui divise sa partie en deux sous-parties plus petites.

La taille du séparateur le plus grand dans une décomposition récursive optimale correspond précisément à la largeur de l'arbre. Pour les problèmes de comptage plus importants, la taille du séparateur le plus grand domine le temps d’exécution, c’est pourquoi cette quantité est si importante.

En ce qui concerne la notion de largeur d'arbre permettant de mesurer la proximité d'un graphique à un arbre, une façon de le rendre intuitif consiste à examiner la dérivation alternative de la décomposition de l'arbre - à partir de la correspondance avec des graphiques en accords. Commencez par trianguler le graphique en parcourant les sommets dans l’ordre et en interconnectant tous les voisins "supérieurs" de chaque sommet.

Construisez ensuite la décomposition de l’arbre en prenant des cliques maximales et en les connectant si leur intersection est un séparateur maximal.

Les approches récursives par séparateur et par triangulation de la décomposition en arborescence sont équivalentes. La largeur de l'arbre + 1 est la taille de la plus grande clique dans la triangulation optimale du graphique, ou si le graphique est déjà triangulé, juste la taille de la plus grande clique.

Ainsi, dans un sens, les graphes en accords de treewidth tw peuvent être considérés comme des arbres où, au lieu de nœuds simples, nous avons des cliques superposés dont la taille est au plus tw + 1. Les graphes non-accords sont de tels "arbres de cliques" avec quelques arêtes de cliques manquantes

Voici quelques graphiques en accords et leur largeur d'arbre.

Yaroslav Bulatov
la source
12
Très belle explication Yaroslav ... Merci beaucoup
Akash Kumar le
4
Une question rapide Yaroslav..Comment as-tu fait de si jolis tableaux? Vous m'avez rappelé combien j'étais inefficace dans l'utilisation des ressources. Je ne savais pas que tu pouvais faire ce genre de choses sur un forum théorique :-). Partager des idées, comment avez-vous fait des choses aussi incroyables? Merci
Akash Kumar le
5
J'ai une collection de scripts Mathematica pour générer des diagrammes comme celui-ci ... pour obtenir le code d'un type de diagramme spécifique, trouvez-en un exemple sur yaroslavvb.blogspot.com ou mathematica-bits.blogspot.com et suivez le lien " Bloc- notes" sur ce poste
Yaroslav Bulatov
6
Cette réponse est tellement géniale. sensationnel.
Toto
le bord 7-10 est-il nécessaire dans le graphique en accords?
J. Schmidt
29

Je crois que Treewidth lui-même a commencé avec le papier de Robertson Seymour déjà donné. Mais certains précurseurs semblent être:

  • Le concept de "dimension" d'un graphe contrôlant le comportement d'algorithmes de programmation dynamique, de Bertelé, Umberto; Brioschi, Francesco (1972), Programmation dynamique non sérielle .

  • Le concept de jeux de poursuite-évasion sur des graphes, de Parsons, TD (1976). "Poursuite-évasion dans un graphique". Théorie et applications des graphes . Springer-Verlag. pp. 426–441. Une variante de celle-ci s'est révélée bien plus tard être équivalente à la largeur d'arbre: Seymour, Paul D .; Thomas, Robin (1993), "Recherche de graphes et théorème min-max pour la largeur d'arbre", Journal of Combinatorial Theory, série B 58 (1): 22–33, doi: 10.1006 / jctb.1993.1027 .

  • Hiérarchies des séparateurs pour les graphes planaires, à partir de Ungar, Peter (1951), "Un théorème sur les graphes planaires", Journal de la London Mathematical Society 1 (4): 256, doi: 10.1112 / jlms / s1-26.4.256 et continu. avec plusieurs articles de Lipton et Tarjan en 1979-1980. La taille du plus grand séparateur dans une hiérarchie de ce type est étroitement liée à la largeur de l'arbre.

Passant à une époque où les idées de Robertson – Seymour ont peut-être déjà commencé à flotter, il existe également un article antérieur à Graph Minors II qui relie explicitement les idées de poursuite-évasion et séparation, et qui définit une notion de largeur équivalente à largeur de chemin : Ellis, JA; Sudborough, IH; Turner, JS (1983), "Séparation de graphes et numéro de recherche", Proc. 1983 Allerton Conf. sur la communication, le contrôle et l’informatique.

David Eppstein
la source
3
Je pense que ce n'est pas vrai: apparemment, Halin avait découvert le concept il y a une dizaine d'années, mais il est resté largement méconnu jusqu'à la redécouverte de Robertson et Seymour. Voir la réponse ci-dessous pour plus de détails.
Hermann Gruber le
21

Dans sa monographie sur la théorie des graphes, Reinhard Diestel fait remonter le concept de largeur et de décomposition d'arbre à un article de Halin datant de 1976 (bien que ces noms ne soient pas utilisés). Il attribue également à cet article le résultat selon lequel les graphiques à grille plane ont une largeur d'arbre illimitée. Bien sûr, il mentionne également le dernier article de Robertson et Seymour, qui "a redécouvert le concept, apparemment pas au courant du travail de Halin" (désolé si ma traduction est mauvaise).

  • Rudolf Halin. Fonctions pour les graphes, J. Geometry 8 (1976): 171–186S
  • Reinhard Diestel. Graphentheorie , 3ème édition allemande, Notizen zu Kapitel 10. (Une édition anglaise du livre est disponible en ligne et peut être téléchargée gratuitement.)
Hermann Gruber
la source
4
Semble assez précis. De Diestel 3ème édition (en anglais), pages 354 à 355: "Les notions de décomposition et de largeur d'arbre ont été introduites pour la première fois (sous différents noms) par R. Halin, fonctions S pour graphes, J. Geometry 8 (1976). , 171 à 186. Entre autres choses, Halin montra que les grilles pouvaient avoir une largeur d'arbre arbitrairement grande. Robertson & Seymour réintroduisirent les deux concepts, apparemment ignorants de l'article de Halin, avec une référence directe à K. Wagner, Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 (1937), 570 à 590. (C’est le document fondateur qui a introduit les décompositions simpliciales en arbres "
András Salamon, le
1
Désolé M. Gruber pour cette réaction très tardive. J'ai vu votre réponse il y a longtemps, je ne savais pas si je pouvais faire d'autres réponses acceptées après en avoir déjà accepté une. Votre réponse est assez précise et semble bien paraître, comme l'a noté M. Salamon également
Akash Kumar
16

La notion de largeur d' arbre [1] (et la notion similaire de largeur de branche ) a été introduite par Robertson et Seymour dans leurs articles phares sur les graph mineurs .

Ils ont d' abord introduit largeur d'arbre afin d'obtenir un test algorithme polynomial si un graphe possède un sous - graphe contractile à un graphe planaire fixe .HGH

Voir: N. Robertson, PD Seymour. Graphique Mineurs. II. Aspects algorithmiques de la largeur de l'arbre . JCT Series B (1986)

Mathieu Chapelle
la source
Merci d'avoir évoqué cette référence. Mais j’étais déjà au courant de cette référence (je savais seulement que c’était un document de Robertson / Seymour - je ne l’avais jamais lu). Je ne savais pas trop ce qui avait amené Robertson, Seymour, à proposer cette notion. Merci d'avoir fait remarquer cela. Mais je cherchais quelque chose allant dans le sens de ce que disait le professeur Eppstein, marquant cela comme la réponse acceptée.
Akash Kumar le
Ow, pas de problème! Le but de ce site est d’obtenir la meilleure réponse à une question et la réponse du professeur Eppstein est bien meilleure!
Mathieu Chapelle