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 z szerokością , Mogę znaleźć (mam nadzieję, że skutecznie) subgraf z z maksymalnym stopniem i treewidth .
Oczywiście powinniśmy wziąć ponieważ nie ma wykresów wysokiej szerokości z maksymalnym stopniem . Dla Wiem, że możesz wziąć takie, że 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 granicanie jest tak dobry, jak bym się spodziewał. Jasne, wiadomo , że można to zrobić (aż do rezygnacji z wydajności obliczeń), ale miałbym nadzieję na coś takiego . Czy można to wykazać na podstawie wykresu szerokości , jest podgrupa o stałym stopniu i liniowej szerokości w ?
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 ...