Jak duża szerokość może mieć drzewo plus połowa jego krawędzi?

14

Niech G będzie drzewem na 2n wierzchołkach. Szerokość grzbietu G, tw (G) = 1. Załóżmy teraz, że dodajemy n krawędzi do G, aby uzyskać wykres H. Łatwa górna granica na tw (H) wynosi n + 1. Czy jest to w zasadzie najlepszy możliwy?

Wydaje się, że tw (H) powinno być O (sqrt (n)), ale jest to tylko niejasne przeczucie. Czy znamy lepsze górne granice niż O (n) dla szerokości wykresu uzyskanej przez dodanie n krawędzi do drzewa na 2n wierzchołkach?

upper-bounds treewidth gphilip
źródło

Odpowiedzi:

18

Twój model nie jest wcale mniej ogólny niż pytanie o arbitralne 3-regularne wykresy, a 3-regularne wykresy ekspanderów mają liniową szerokość. Więc nie wiem o stałych czynnikach, ale Θ (n) jest najlepsze z możliwych, tak.

David Eppstein
źródło
3
Dzięki, to odpowiada na moje pytanie. Aby nieco rozwinąć odpowiedź Davida, niech H będzie połączonym 3-regularnym wykresem na 2n wierzchołkach. H ma wtedy krawędzie 3n. Niech G będzie drzewem na 2n wierzchołkach uzyskanych przez usunięcie n + 1 krawędzi z H. Dodanie n tych krawędzi z powrotem do G da nam H '= (H minus jedna krawędź). Pozwalając H być wykresem ekspandera z treewidth \ theta (n), widzimy, że H 'ma również treewidth \ theta (n).
gphilip
8

Jak zauważył David, w zasadzie pytasz o granice szerokości linii połączonego wykresu ze średnim stopniem 3. W bardziej szczególnym przypadku grafów 3-regularnych można uzyskać następujące dolne i górne granice. Wyznaczając przez pw (G) szerokość ścieżki wykresu G, jest to jasne

(1) tw (G) <= pw (G) dla dowolnego wykresu G (ponieważ rozkład ścieżki jest rozkładem drzewa)

Udowodniono to w [1], że

(2) Dla każdego \ epsilon> 0 istnieje liczba całkowita n_0 taka, że ​​dla każdego 3-regularnego wykresu G na n> = n_0 wierzchołkach pw (G) <= n / 6 + \ epsilon * n.

Daje to górną granicę około n / 6 na szerokości 3-regularnych wykresów.

Dla prawie pewnej dolnej granicy cytuję z [2]:

„Ponieważ losowe wykresy sześcienne prawie na pewno mają szerokość bisekcji co najmniej 0,101 n (Kostochka, Melnikov, 1992), prawie na pewno nie mają separatora wielkości mniejszego niż n / 20”, a zatem prawie na pewno nie ma rozkładu drzewa o szerokości mniejszej niż n / 20 .

Dla „pewnej” dolnej granicy szerokości bisekcji [3] pokazuje nieskończoną rodzinę 3-regularnych wykresów, tak że każdy wykres G = (V, E) w tej rodzinie ma szerokość bisekcji co najmniej 0,082 * | V |.

[1] Fedor V. Fomin, Kjartan Høie: Ścieżka wykresów sześciennych i dokładne algorytmy. Inf. Proces. Łotysz. 97 (5): 191–196 (2006)

[2] Jaroslav Nesetril, Patrice Ossona de Mendez: Grad i klasy z ograniczoną ekspansją II. Aspekty algorytmiczne. Eur. J. Comb. 29 (3): 777–791 (2008)

[3] Siergiej L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: Nowe spektralne dolne granice szerokości bisekcji wykresów. Teoria Comput. Sci. 320 (2-3): 155-174 (2004)

Serge Gaspers
źródło
Dziękuję Serge. Na tym etapie granica związana z przepustowością jest prawdopodobnie dla mnie bardziej dostępna niż ta z wykorzystaniem grafów ekspanderów; Jednak nie przeczytałem jeszcze żadnego dowodu.
gphilip