Zmniejszanie rozkładu drzewa o minimalnej szerokości w czasie wielomianowym

Jak dobrze wiadomo, rozkład drzewa wykresu składa się z drzewa ze skojarzoną torbą dla każdego wierzchołka , który spełnia następujące warunki: $G$ $T$ $T_v \subseteq V(G)$ $v \in V(T)$

Każdy wierzchołek występuje w jakimś workiem . $G$ $T$
Dla każdej krawędzi znajduje się worek zawierający oba punkty końcowe krawędzi. $G$
Dla każdego wierzchołka , torebki zawierające indukuje podłączony poddrzewo . $v \in V(G)$ $v$ $T$

Z naszego rozkładu możemy również wymagać następującego warunku, zwanego chudością :

Dla każdej pary torby , z , jeśli i z , a następnie albo a) istnieje ścieżek rozłącznych wierzchołków w , lub b) drzewo zawiera krawędź na ścieżce od węzła do węzła tak że a zestaw przecina wszystkie ścieżkami . $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 pokazał, że zawsze istnieje rozkład drzew o minimalnej szerokości, który jest również szczupły, a kilku autorów przedstawiło prostsze dowody tego faktu, na przykład Patrick Bellenbaum i Reinhard Diestel .

Co jestem zainteresowany jest następujący: podany wykres $G$ i drzewo dekompozycji minimalnej szerokości $G$ , możemy znaleźć minimalną szerokość chudego drzewo dekompozycji $G$ w czasie wielomianowym?

Dwa wymienione dowody nie zapewniają tak efektywnej konstruktywności. W artykule Bellenbauma i Diestela wspomniano, że „Kolejny (bardziej konstruktywny) krótki dowód twierdzenia Thomasa został podany w P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000”. Niestety nie udało mi się znaleźć manuskryptu online, a mój niemiecki nie jest taki świetny.

ds.algorithms graph-theory graph-algorithms treewidth Bart Jansen
źródło

Fajne pytanie. Znalezienie rozkładu drzewa o minimalnej szerokości jest trudne dla NP, więc twój problem jest nieco źle postawiony (wydaje się). Domyślam się, że można o to zapytać w przypadku ograniczonej szerokości pleców lub w przybliżeniu.

Chandra Chekuri,

Ale w jego przypadku jest on podany na min-width drzewo dekompozycji i chce algorytm, aby pochylić.

Suresh Venkat,

@SureshVenkat: Zdaję sobie sprawę, że ma rozkład drzewa o minimalnej szerokości, ale jak możesz w ogóle sprawdzić, czy jest poprawny? Co więcej, rozkład chudego drzewa dostosowuje się lokalnie do szerokości różnych części wykresu, więc optymalny rozkład drzewa na wykresie globalnym nie pozwala uniknąć trudności ze znalezieniem szerokości miejscowych elementów.

Chandra Chekuri,

Gładkie rozkłady drzew (gdzie wszystkie torby mają ten sam rozmiar, a dwie sąsiednie torby różnią się dokładnie jednym wierzchołkiem) są znacznie łatwiejsze w obsłudze niż ogólne rozkłady drzew, i łatwo zauważyć, że rozkład drzewa o minimalnej szerokości jest gładki . Więc może uda ci się uzyskać wydajną konstrukcję, ograniczając jedną ze znanych konstrukcji do nich. Czy zawsze istnieje rozkład drzewa o minimalnej szerokości, który jest gładki i chudy?

Diego de Estrada,

@ChandraChekuri Zakładam, że problem weryfikacji zniknie, jeśli określisz to jako problem obiecujący, ale rozumiem, że masz rację, że rozkład jednego drzewa niekoniecznie daje ci wystarczającą ilość informacji do dostosowania. Ale możliwe jest następujące pytanie: czy istnieje sposób „lokalnie” zmodyfikować rozkład danego drzewa, aby „pochylił się” bez zwiększania szerokości grzbietu?

Suresh Venkat,

Oto formalny powód, dla którego problem nie jest rozwiązany w czasie wielorakim, chyba że P = NP. Wiemy, że znalezienie szerokości danego wykresu to NP-Hard. Na podstawie wykresu możemy dodać rozłączną klikę o rozmiarze aby utworzyć nowy wykres . A min szerokości drzewa rozkładu można otrzymać w następujący sposób: ma dwa węzły z jednego worka, zawierającego wszystkie węzły klika drugi zawierający wszystkie węzły . Teraz czyni to drzewa dekompozycji chude wymagałoby znalezienia rozkładu chudego drzewo oryginalnego grafu , która, jako produkt uboczny, otrzymując treewidth z . $G$ $V(G)+1$ $G'$ $G'$ $G$ $G$ $G$

Chandra Chekuri
źródło

Słuszna uwaga. Czy wiesz, czy coś wiadomo na temat algorytmów sparametryzowanych i / lub umiarkowanie wykładniczych w celu znalezienia rozkładu chudego drzewa?

Bart Jansen,

Zmniejszanie rozkładu drzewa o minimalnej szerokości w czasie wielomianowym

Odpowiedzi: