Znajdowanie podgrafów o wysokiej szerokości i stałym stopniu

9

Dano mi wykres z szerokością i dowolnym stopniem, i chciałbym znaleźć podrozdział z (niekoniecznie indukowany podsgraf) taki, że ma stały stopień, a jego szerokość jest tak wysoka, jak to możliwe. Formalnie mój problem jest następujący: po wybraniu stopnia związanego , jaka jest najlepsza funkcja tak że na dowolnym wykresieG kHGHdNf:NNG z szerokością k, Mogę znaleźć (mam nadzieję, że skutecznie) subgraf H z G z maksymalnym stopniem d i treewidth f(k).

Oczywiście powinniśmy wziąć d3 ponieważ nie ma wykresów wysokiej szerokości z maksymalnym stopniem <3. Dlad=3 Wiem, że możesz wziąć f takie, że f(k)=Ω(k1/100)lub mniej więcej, odwołując się do drobnego wyniku ekstrakcji siatki Chekuri i Chuzhoya (i używając go do wyodrębnienia wykresu wysokiej-3-krotności stopnia, np. ściany, jako topologii drobnej), przy czym możliwe jest obliczenie subgrafu (w RP ). Jednak jest to bardzo mocny wynik z rozbudowanych dowodu, więc czuje się źle, aby używać go za to, co wygląda na znacznie prostszą problemu: Chciałbym jak znaleźć żadnej stałej stopni wysokiej treewidth podgrafu, a nie jeden specyficzny jak w ich wyniku. Dalej granicafnie jest tak dobry, jak bym się spodziewał. Jasne, wiadomo , że można to zrobićΩ(k1/20) (aż do rezygnacji z wydajności obliczeń), ale miałbym nadzieję na coś takiego Ω(k). Czy można to wykazać na podstawie wykresuG szerokości k, jest podgrupa G o stałym stopniu i liniowej szerokości w k?

Interesuje mnie również to samo pytanie dotyczące szerokości ścieżki, a nie szerokości. Jeśli chodzi o przepustowość, nie znam żadnego analogu do drobnej ekstrakcji siatki, więc problem wydaje się jeszcze bardziej tajemniczy ...

a3nm
źródło

Odpowiedzi:

12

Zobacz artykuł Julii Chuzhoy i mnie na temat sparyfikatorów Treewidth. Pokazujemy, że można uzyskać podgrupa stopnia co najwyżej 3 z szerokościąΩ(k/polylog(k)) gdzie k jest szerokość G. https://arxiv.org/abs/1410.1016 Dowód jest krótszy niż w przypadku nieletnich, ale nadal nie jest to takie łatwe i opiera się na kilku poprzednich narzędziach.

Załóżmy, że decydujesz się na łatwiejszy cel - stopień 4 i szerokość Ω(k1/4)wtedy możesz go zdobyć o wiele łatwiej dzięki Reedowi i Drewnu na nieletnich podobnych do siatki. https://arxiv.org/abs/0809.0724

Innym łatwym rezultatem, który można uzyskać, jest punkt wyjścia dla niektórych bardziej zaangażowanych dowodów. Możesz dostać podgraph degre log2(k) i treewidth Ω(k/polylog(k)). Możesz zobaczyć papier sparyfikatora treewidth dla argumentu, aby to osiągnąć.

Chandra Chekuri
źródło
1
Dodatkowy komentarz. Czy można uzyskać subgrafΩ(k)szerokość i stały stopień to bardzo interesujący otwarty problem. Zadajemy to pytanie w artykule na temat treewidth sparsifier, ale nie mamy dobrego zrozumienia właściwej odpowiedzi. Ciekawym wykresem, o który pytał Bart Jansen, jest hipersześciann węzły, które mają szerokość Θ(n/logn) i stopień początkowy Θ(logn).
Chandra Chekuri
Dzięki za wskazanie Reeda i Wooda! Podam szczegóły. 1.2 ich artykułu mówi, że wykres G z szerokościąΩ(l4polylog(l))zawiera siatkę mniejszą rzędu l. Teraz siatka M-podrzędna M jest podgrafem G utworzonym ze ścieżek z dwustronnym wykresem przecięcia H, więc każdy wierzchołek w M należy do co najwyżej 2 ścieżek M (w przeciwnym razie jest to trójkąt w H), stąd M ma maksymalny stopień 4. Ponadto M ma szerokość grzbietuΩ(l): w rzeczywistości każdy rozkład drzewa o szerokości M k daje rozkład drzewa o szerokości <= 2k (zastępując każdy wierzchołek ścieżkami składowymi, najwyżej 2), a H ma Kljako nieletni.
a3nm
Ponownie, jest to bardzo pomocne, dziękuję. Ciekawe, że pytanie o liniową szerokość jest wciąż otwarte. (To powiedziawszy, jeśli dobrze rozumiem, Hipoteza 1.2 w twoim dokumencie sparsyfikatora dotyczy nieco innego problemu: wymaga, aby podgrupa była poddziałem jakiegoś H wielkości wielomianowej w k, podczas gdy nie pytam o to i po prostu chcę wykres podrzędny ma mieć stały stopień.) Ostatnia rzecz: czy wiesz coś o tym otwartym problemie, ale o szerokości, a nie szerokości? Dzięki jeszcze raz!
a3nm
@ a3nm, dlaczego jesteś zaskoczony, że kwestia liniowej szerokości jest otwarta? Obecnie nie mamy stałego przybliżenia współczynnika dla szerokości. Jeśli chodzi o szerokość ścieżki, w tej chwili jedynym sposobem na przybliżenie szerokości ścieżki jest związek między ścieżką i szerokością ścieżki, która pokazujetw(G)pw(G)O(logn)tw(G). Poprzez sparifikację szerokości można uzyskać sparifikację szerokości ścieżki, ale tracimy współczynnik log n. Byłoby miło, gdyby był to tylko współczynnik log pw (G), ale nie jestem pewien, jak to zrobić ani czy jest znany.
Chandra Chekuri
Dziękuję za wyjaśnienia dotyczące statusu szerokości linii, a także za wyjaśnienia dotyczące sparametryzowania ścieżki. Ostatnią rzeczą, o której wspomniałeś, są wyniki, których potrzebowalibyśmy; szkoda, że ​​pytanie jest nadal otwarte. W każdym razie jeszcze raz bardzo dziękuję za wyjaśnienia!
a3nm