Geneza pojęcia treewidth

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.

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.)

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.

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.

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).

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 .

$G$$H$

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