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

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 wykresie$G$ $k$$H$$G$$H$$d \in \mathbb{N}$$f : \mathbb{N} \to \mathbb{N}$$G$ z szerokością $k$, Mogę znaleźć (mam nadzieję, że skutecznie) subgraf $H$ z $G$ z maksymalnym stopniem $\leq d$ i treewidth $f(k)$.

Oczywiście powinniśmy wziąć $d \geq 3$ ponieważ nie ma wykresów wysokiej szerokości z maksymalnym stopniem $<3$. Dla$d = 3$ Wiem, że możesz wziąć $f$ takie, że $f(k) = \Omega(k^{1/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 granica$f$nie jest tak dobry, jak bym się spodziewał. Jasne, wiadomo , że można to zrobić$\Omega(k^{1/20})$ (aż do rezygnacji z wydajności obliczeń), ale miałbym nadzieję na coś takiego $\Omega(k)$. Czy można to wykazać na podstawie wykresu$G$ 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 ...

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ą$\Omega(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ść $\Omega(k^{1/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 $\log^2(k)$ i treewidth $\Omega(k/\mathsf{polylog}(k))$. Możesz zobaczyć papier sparyfikatora treewidth dla argumentu, aby to osiągnąć.