Geneza pojęcia treewidth

61

Moje dzisiejsze pytanie jest (jak zwykle) trochę głupie; ale prosiłbym cię o pomyślne rozważenie.

Chciałem wiedzieć o genezie i / lub motywacji leżącej u podstaw koncepcji treewidth. Z pewnością rozumiem, że jest on stosowany w algorytmach FPT, ale nie sądzę, że to był powód, dla którego zdefiniowano to pojęcie.

Pisałem do góry notatki Scribe na ten temat w klasie prof Robin Thomas . Wydaje mi się, że rozumiem niektóre zastosowania tej koncepcji (ponieważ przenosi ona właściwości separacyjne drzewa na rozkład wykresu), ale z jakiegoś powodu nie jestem przekonany, że powodem, dla którego opracowano tę koncepcję, był pomiar bliskości wykresu do drzewa.

Postaram się wyjaśnić (nie jestem pewien, czy mogę, proszę dać mi znać, jeśli pytanie nie jest jasne). Chciałbym wiedzieć, czy podobne pojęcia istniały gdzie indziej w jakiejś innej gałęzi matematyki, skąd pojęcie to zostało rzekomo „zapożyczone”. Domyślam się, że będzie to topologia - ale z powodu mojego braku wiedzy nie mogę nic powiedzieć.

Głównym powodem, dla którego jestem tego ciekawy, byłby - po raz pierwszy czytam jego definicję, nie byłem pewien, dlaczego i jak ktokolwiek mógłby ją sobie wyobrazić i do jakiego celu. Jeśli pytanie nie jest jeszcze jasne, w końcu spróbuję to sformułować w ten sposób - udawajmy, że pojęcie treewidth nie istnieje. Jakie naturalne pytania (lub rozszerzenia niektórych twierdzeń / pojęć matematycznych) do dyskretnych ustawień doprowadzą do wyobrażenia sobie definicji (pozwólcie, że użyję tego słowa) jako treewidtha.

Akash Kumar
źródło
2
fyi link do notatek skryptu dostaje błąd 403 zabroniony.
vzn

Odpowiedzi:

58

Jeśli naprawdę chcesz wiedzieć, co doprowadziło mnie i Neila Robertsona do szerokości drzewa, to wcale nie były algorytmy. Próbowaliśmy rozwiązać przypuszczenie Wagnera, że ​​na dowolnym nieskończonym zestawie grafów jeden z nich jest niewielki względem drugiego i mieliśmy rację na początku. Wiedzieliśmy, że to prawda, jeśli ograniczymy się do wykresów bez ścieżki k-wierzchołków; pozwól mi wyjaśnić dlaczego. Wiedzieliśmy, że wszystkie takie wykresy mają prostą strukturę (dokładniej, każdy wykres bez ścieżki k-wierzchołków ma tę strukturę, a każdy wykres z tą strukturą nie ma ścieżki 2 ^ k-wierzchołków); i wiedzieliśmy, że na każdym nieskończonym zestawie grafów, wszystkie o tej strukturze, jeden z nich był niewielki względem drugiego. Zatem hipoteza Wagnera była prawdziwa dla grafów z ograniczeniem ich maksymalnej długości ścieżki.

Wiedzieliśmy również, że jest to prawdą w przypadku grafów bez gwiazdy k jako pomniejszej, ponownie, ponieważ mieliśmy twierdzenie o strukturze dla takich grafów. Próbowaliśmy szukać bardziej ogólnych nieletnich, którzy mieliby odpowiednie twierdzenia o strukturze, których moglibyśmy użyć, aby udowodnić przypuszczenie Wagnera, i które doprowadziły nas do szerokości ścieżki; wyklucz DOWOLNE drzewo jako mniejsze, a otrzymasz ograniczoną szerokość ścieżki, a jeśli masz ograniczoną szerokość ścieżki, to są drzewa, których nie możesz mieć jako podrzędne. (To było dla nas trudne twierdzenie; mieliśmy niesamowicie twardy dowód w pierwszym artykule Graph Minors, nie czytaj go, można to uczynić znacznie łatwiejszym.) Ale możemy udowodnić hipotezę Wagnera dla grafów z ograniczoną szerokością ścieżki, a to oznaczało, że tak było w przypadku wykresów niezawierających żadnego ustalonego drzewa jako pomniejszego; duże uogólnienie ścieżki i przypadków gwiazd, o których wspominałem wcześniej.

W każdym razie, po zrobieniu tego, staraliśmy się iść dalej. Nie mogliśmy zrobić ogólnych wykresów, więc pomyśleliśmy o wykresach płaskich. Znaleźliśmy twierdzenie o strukturze dla grafów płaskich, które nie zawierały żadnego ustalonego grafu płaskiego jako pomniejszego (było to łatwe); była ograniczona szerokością drzewa. Udowodniliśmy, że dla każdego stałego wykresu płaskiego wszystkie wykresy płaskie, które nie zawierały go jako drobne, ograniczały szerokość drzewa. Jak możesz sobie wyobrazić, to było naprawdę ekscytujące; przez przypadek twierdzenie o strukturze wykluczania grafów płaskich (wewnątrz większych wykresów płaskich) było naturalnym odkryciem twierdzenia o strukturze wykluczania drzew (wewnątrz grafów ogólnych). Czuliśmy, że robimy coś dobrze. I to pozwala nam udowodnić hipotezę Wagnera dla wszystkich grafów płaskich, ponieważ mieliśmy takie twierdzenie o strukturze.

Ponieważ szerokość drzewa działała na rzecz wykluczania wykresów płaskich w większych wykresach płaskich, było naturalne pytanie, czy działała na rzecz wykluczania wykresów płaskich wewnątrz wykresów niepłaskich - czy to prawda, że ​​dla każdego stałego wykresu płaskiego wszystkie wykresy nie zawierające go jako drobne ograniczyło szerokość drzewa? Tego długo nie mogliśmy udowodnić, ale w ten sposób zaczęliśmy myśleć o szerokości drzew ogólnych wykresów. Kiedy już mieliśmy pojęcie szerokości drzewa, było całkiem jasne, że jest dobre dla algorytmów. (I tak, nie mieliśmy pojęcia, że ​​Halin już myślał o szerokości drzewa.)

Paul Seymour
źródło
18
Witamy w cstheory i dziękuję za świetną odpowiedź!
Suresh Venkat
Bardzo dziękuję za poświęcony czas, profesorze Seymour. Ta odpowiedź jest pełna wnikliwych spostrzeżeń i obejmuje część historyczną, którą pierwotnie zamierzało pytanie. Oznaczając to jako zaakceptowaną odpowiedź :)
Akash Kumar,
61

Oto, jak sam możesz wymyślić koncepcję szerokości drzewa.

Załóżmy, że chcesz policzyć liczbę niezależnych zestawów na poniższym wykresie.

Niezależne zestawy można podzielić na te, w których jest zajęty górny węzeł i te, w których nie jest zajęty

Teraz zauważ, że wiedząc, czy górny węzeł jest zajęty, możesz policzyć liczbę niezależnych zestawów w każdym podproblemie osobno i pomnożyć je. Powtarzanie tego procesu rekurencyjnie daje algorytm zliczania niezależnych zestawów opartych na separatorach grafów.

Załóżmy, że nie masz już drzewa. Oznacza to, że separatory są większe, ale możesz użyć tego samego pomysłu. Rozważ policzenie niezależnych zestawów na poniższym wykresie.

Skorzystaj z tego samego pomysłu podzielenia problemu na podproblemy na separatorze, otrzymasz następujące

Podobnie jak w poprzednim przykładzie, każdy termin w sumie rozkłada się na dwa mniejsze zadania liczenia w separatorze.

Zauważ, że w sumie mamy więcej terminów niż w poprzednim przykładzie, ponieważ musimy wyliczyć wszystkie konfiguracje na naszym separatorze, który może potencjalnie rosnąć wykładniczo wraz z rozmiarem separatora (w tym przypadku rozmiar 2).

Rozkład drzewa to struktura danych umożliwiająca kompaktowe przechowywanie tych rekurencyjnych etapów partycjonowania. Rozważ poniższy wykres i jego rozkład drzewa

Aby policzyć przy użyciu tego rozkładu, najpierw naprawiłeś wartości w węzłach 3,6, co dzieli je na 2 podproblemy. W pierwszym podproblemie dodatkowo naprawiłeś węzeł 5, który dzieli jego część na dwie mniejsze części.

Rozmiar największego separatora w optymalnym rekurencyjnym rozkładzie to dokładnie szerokość drzewa. W przypadku większych problemów z liczeniem, rozmiar największego separatora dominuje w środowisku wykonawczym, dlatego ta ilość jest tak ważna.

Jeśli chodzi o pojęcie pomiaru szerokości drzewa, jak blisko wykresu jest drzewo, jednym ze sposobów uczynienia go intuicyjnym jest przyjrzenie się alternatywnemu wyprowadzeniu rozkładu drzewa - na podstawie zgodności z wykresami akordowymi. Najpierw trianguluj wykres, wykonując ruchy wierzchołków w kolejności i łącząc wszystkich „wyżej uporządkowanych” sąsiadów każdego wierzchołka.

Następnie skonstruuj rozkład drzewa, biorąc maksymalne kliky i łącząc je, jeśli ich przecięcie jest maksymalnym separatorem.

Podejścia oparte na separatorze rekurencyjnym i triangulacji do konstruowania rozkładu drzewa są równoważne. Szerokość drzewa + 1 to rozmiar największej kliki w optymalnej triangulacji wykresu, lub jeśli wykres jest już triangulowany, wystarczy rozmiar największej kliki.

W pewnym sensie akordowe wykresy szerokości grzbietu tw można traktować jako drzewa, w których zamiast pojedynczych węzłów mamy nakładające się kliki wielkości co najwyżej tw + 1. Nie-akordowe wykresy to takie „drzewa kliki”, w których brakuje niektórych krawędzi kliki

Oto kilka wykresów akordowych i ich szerokość drzewa.

Jarosław Bułatow
źródło
12
Bardzo miłe wyjaśnienie Jarosław ... Wielkie dzięki
Akash Kumar
4
Szybkie pytanie Jarosław .. Jak narysowałeś takie ładne zdjęcia? Sprawiłeś, że przypomniałem sobie, jak nieefektywnie wykorzystuję zasoby. Nie wiedziałem, że możesz robić rzeczy tak fajnie na forum teorii :-). Udostępnianie myśli, jak zrobiłeś takie niesamowite rzeczy? Dzięki
Akash Kumar
5
Mam kolekcję skryptów Mathematica do generowania takich diagramów ... aby uzyskać kod dla określonego typu diagramu, znajdź jego przykład na yaroslavvb.blogspot.com lub mathematica-bits.blogspot.com i kliknij link „Notatnik” na ten post
Jarosław Bułatow
6
Ta odpowiedź jest niesamowita. łał.
toto
czy krawędź 7-10 jest niezbędna na wykresie akordowym?
J. Schmidt
29

Wierzę, że sama treewidth rozpoczęła się od już podanego dokumentu Robertsona Seymoura. Ale niektóre wcześniejsze prekursory wydają się:

  • Pojęcie „wymiaru” wykresu, który kontrolowałby zachowanie dynamicznych algorytmów proogramowania na nim, z Bertelé, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming .

  • Koncepcja gier polegających na unikaniu pościgu na wykresach, autorstwa Parsons, TD (1976). „Unikanie pościgu na wykresie”. Teoria i zastosowania wykresów . Springer-Verlag. s. 426–441. Jeden wariant tego okazał się znacznie późniejszy niż treewidth: Seymour, Paul D .; Thomas, Robin (1993), „Wyszukiwanie wykresów i twierdzenie min-max dla szerokości drzewa”, Journal of Combinatorial Theory, Series B 58 (1): 22–33, doi: 10.1006 / jctb.1993.1027 .

  • Hierarchie separatorów dla wykresów planarnych, poczynając od Ungar, Peter (1951), „Twierdzenie o wykresach planarnych”, Journal of the London Mathematical Society 1 (4): 256, doi: 10.1112 / jlms / s1-26.4.256 , i kontynuując z kilkoma artykułami Liptona i Tarjana w latach 1979–1980. Rozmiar największego separatora w hierarchii tego typu jest ściśle związany z szerokością.

Przechodząc do czasów, w których idee Robertsona-Seymoura mogły już zacząć się krążyć wokół, istnieje także artykuł wcześniejszy niż Graph Minors II, który wyraźnie łączy idee pościgowe i unikania i separacji, i który definiuje pojęcie szerokości równoważnej szerokości ścieżki : Ellis, JA; Sudborough, IH; Turner, JS (1983), „Separacja wykresów i numer wyszukiwania”, Proc. 1983 Allerton Conf. w sprawie komunikacji, kontroli i informatyki.

David Eppstein
źródło
3
Myślę, że to nieprawda: najwyraźniej Halin odkrył tę koncepcję jakieś dziesięć lat wcześniej, ale pozostało to w dużej mierze niezauważone aż do ponownego odkrycia Robertsona i Seymour. Szczegóły znajdują się w odpowiedzi poniżej.
Hermann Gruber,
21

W swojej monografii dotyczącej teorii grafów Reinhard Diestel prześledził koncepcję treewidth i rozkładów drzew z powrotem do artykułu Halina z 1976 r. (Aczkolwiek nie używającego tych nazw). Przypisuje także temu artykułowi, że płaskie wykresy siatki mają nieograniczoną szerokość. Oczywiście wspomina także późniejszy artykuł Robertsona i Seymoura, który „odkrył na nowo koncept, oczywiście nieświadomy pracy Halina” (przepraszam, jeśli moje tłumaczenie jest słabe).

  • S
  • Reinhard Diestel. Graphentheorie , 3. wydanie niemieckie, Notizen zu Kapitel 10. (Niektóre angielskie wydanie książki jest dostępne online do pobrania za darmo).
Hermann Gruber
źródło
4
Wydaje się dość dokładne. Z trzeciego wydania (Diestel) (str. 354–355): „Pojęcia rozkładu drzewa i szerokości drzewa zostały po raz pierwszy wprowadzone (pod różnymi nazwami) przez R. Halina, funkcje S dla wykresów, J. Geometry 8 (1976) , 171–186. Halin wykazał między innymi, że siatki mogą mieć dowolnie dużą szerokość drzewa. Robertson i Seymour ponownie wprowadzili te dwie koncepcje, najwyraźniej nieświadome pracy Halina, z bezpośrednim odniesieniem do K. Wagnera, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590. (Jest to przełomowy artykuł, który wprowadził prosty rozkład drzew ”
András Salamon,
1
Przepraszam pana Gruber za tę super późną reakcję. Widziałem twoją odpowiedź dawno temu, nie byłem pewien, czy mógłbym zaakceptować inne odpowiedzi po tym, jak już je zaakceptowałem. Twoja odpowiedź jest dość dokładna i wygląda na martwą, jak zauważył również pan Salamon
Akash Kumar
16

Pojęcie szerokości drzewa [1] (i podobne pojęcie szerokości gałęzi ) zostało wprowadzone przez Robertsona i Seymour w ich najważniejszych artykułach na temat Graph Minors .

GH

Patrz: N. Robertson, PD Seymour. Wykres Nieletni. II. Algorytmiczne aspekty szerokości drzewa . JCT Series B (1986)

Mathieu Chapelle
źródło
Dzięki za zapoznanie się z tym odniesieniem. Ale byłem już świadomy tego odniesienia (po prostu wiedziałem, że to był jakiś artykuł Robertsona / Seymour - nigdy go nie przeczytałem). Po prostu nie byłem pewien, co skłoniło Robertsona, Seymoura do stworzenia tego pojęcia. Dzięki za zwrócenie na to uwagi. Ale szukałem czegoś podobnego do tego, co powiedział prof. Eppstein, więc oznaczam to jako przyjętą odpowiedź.
Akash Kumar
Ow, nie ma problemu! Celem tej witryny jest uzyskanie najlepszej odpowiedzi na pytanie, a odpowiedź prof. Eppsteina pasuje znacznie lepiej!
Mathieu Chapelle,