Jakie jest najważniejsze pojęcie rzadkości w projektowaniu wydajnych algorytmów graficznych?

Istnieje kilka konkurencyjnych pojęć „rzadkiego wykresu”. Na przykład wykres, który można osadzić na powierzchni, można uznać za rzadki. Lub wykres z ograniczoną gęstością krawędzi. Lub wykres z wysokim obwodem. Wykres z dużym rozszerzeniem. Wykres z ograniczoną szerokością. (Nawet w obrębie podpól losowych wykresów jest nieco niejednoznaczne co do tego, co można nazwać rzadkim.) Et cetera.

Jakie pojęcie „grafu rzadkiego” miało największy wpływ na projektowanie wydajnych algorytmów graficznych i dlaczego? Podobnie, jakie pojęcie „gęsty wykres” ...? (Uwaga: Karpiński dużo pracował nad wynikami aproksymacji dla jednego standardowego modelu gęstych grafów.)

Właśnie widziałem przemówienie J. Nesetrila na temat jego programu (wraz z P. Ossoną de Mendez), aby uchwycić miary rzadkości na wykresach w zunifikowanym (asymptotycznym) systemie. Moje pytanie - tak, być może dość subiektywne i spodziewam się różnych obozów - jest motywowane chęcią uchwycenia wieloaspektowej perspektywy wykorzystania rzadkości w algorytmach (i uzupełnienia wszelkich luk w moim zrozumieniu tego problemu).

Myślę, że według jakiegokolwiek rozsądnego standardu trójwymiarowy wykres siatki n × n × n musiałby być uważany za rzadki i wyklucza to większość definicji kandydatów obejmujących osadzanie na powierzchni lub drobne. (Podliniowa szerokość grzbietu byłaby jednak nadal możliwa).

Moją ulubioną miarą rzadkości jest zwyrodnienie . Degeneracja wykresu stanowi minimum, we wszystkich liniowych porządkach wierzchołków wykresu, maksymalnego przekroczenia w ukierunkowanej acyklicznej orientacji wykresu utworzonej przez zorientowanie każdej krawędzi od wcześniejszych do późniejszych wierzchołków w uporządkowaniu. Równolegle jest to maksymalny, we wszystkich podgraphach, minimalny stopień w podgrodzie. Na przykład wykresy płaskie mają degenerację pięć, ponieważ każdy podgrupa wykresu płaskiego ma wierzchołek stopnia co najwyżej pięć. Degenerację można łatwo obliczyć w czasie liniowym, a uporządkowanie liniowe wynikające z definicji jest przydatne w algorytmach .

Degeneracja mieści się w stałym współczynniku niektórych innych standardowych miar, w tym arboryczności, grubości i maksymalnego średniego stopnia dowolnego podgrupy, ale myślę, że są one trudniejsze w użyciu.

Wydaje się, że istnieje wiele „dobrych” pojęć rzadkości, ale istnieje coś w rodzaju hierarchii dla tych strukturalnych pojęć rzadkości, które mają charakter teoretyczny. Myślę, że miały one duży wpływ na wydajne algorytmy graficzne.

$k$$K_{k+2}$

Notatki z kursu Anuj Dawara z listopada 2010 r. Również omawiają lokalnie ograniczoną szerokość, która jest nieporównywalna z wykluczonymi małoletnimi. Ograniczony stopień wyraźnie definiuje rzadkie wykresy, a takie wykresy ograniczyły lokalną szerokość, ale nie są możliwe do zdefiniowania przez zestaw wykluczonych nieletnich.

Wpływ ograniczonego stopnia jest wyraźny: często jest to jedno z pierwszych ograniczeń, które sprawia, że ​​trudny problem można rozwiązać, na przykład algorytm Luksa dla izomorfizmu grafów na wykresach z ograniczonym stopniem. Wpływ wykluczenia małoletniego jest również wyraźny, przynajmniej w postaci ograniczonej szerokości (jak zauważył Suresh).

Pojęcie lokalnego wykluczenia drobnego uogólnia zarówno lokalnie ograniczoną szerokość pleców, jak i wykluczonych nieletnich, tworząc w ten sposób „najbardziej ogólną” klasę w hierarchii. Jednak nie jest jeszcze jasne, jak wykorzystać tę właściwość w praktycznych algorytmach. Nawet „możliwy do usunięcia” przypadek wykluczenia małoletniego niekoniecznie ma dobre praktyczne algorytmy; duże stałe występują w algorytmach teoretycznych. Mam nadzieję, że na dłuższą metę okaże się, że niektóre z tych klas będą miały praktycznie wydajne algorytmy.

Zobacz także moją odpowiedź, co jest łatwe dla niewielkich wykluczonych wykresów? dla dalszych powiązanych uwag.

Nie mogę wymyślić żadnej właściwości wykresu, która miałaby tak duży wpływ na projektowanie wydajnych algorytmów, jak ograniczona szerokość i ogólnie dwuwymiarowość.

Można myśleć o grafie jako o macierzy przylegania - istnieje kilka definicji rzadkości macierzy (na przykład% zerowych wpisów), które mogłyby przełożyć się z powrotem na sam wykres. Poza% zerowych wpisów, szerokość pasma macierzy przy zmianie kolejności może być dobrym wskaźnikiem rzadkości grafów (wygląda na to, że szerokość pasma jest związana ze zwyrodnieniem).