Ograniczona ekspansja - Bounded expansion
W teorii grafów mówi się , że rodzina grafów ma ograniczoną ekspansję, jeśli wszystkie jej płytkie podrzędne są grafami rzadkimi . Wiele naturalnych rodzin rzadkich grafów ma ograniczoną ekspansję. Ściśle powiązana, ale silniejsza własność, rozwinięcie wielomianowe , jest równoważna istnieniu twierdzeń o separatorach dla tych rodzin. Rodziny z tymi własnościami mają wydajne algorytmy rozwiązywania problemów, w tym problemu izomorfizmu podgrafów i sprawdzania modelu dla teorii grafów pierwszego rzędu.
Definicja i równoważne charakterystyki
A T -shallow drobne grafu G określa się wykres utworzony z G poprzez zaciągnięcie zbiór subgraphs wierzchołek-rozłącznych o promieniu t i usuwanie pozostałych wierzchołków G . Rodzina grafów ma rozwinięcie ograniczone, jeśli istnieje funkcja f taka, że w każdym t -płytkim molowym grafu w rodzinie stosunek krawędzi do wierzchołków wynosi co najwyżej f ( t ).
Równoważne definicje klas ograniczonych rozwinięć są takie, że wszystkie płytkie podrzędne mają liczbę chromatyczną ograniczoną funkcją t , lub że dana rodzina ma ograniczoną wartość parametru topologicznego . Taki parametr jest niezmiennikiem grafu, który jest monotonny przy wykonywaniu podgrafów, tak że wartość parametru może zmieniać się tylko w kontrolowany sposób, gdy graf jest podzielony, i taki, że wartość ograniczonego parametru implikuje, że graf ma ograniczoną degenerację .
Twierdzenia o rozwinięciu wielomianowym i separatorach
Silniejszym pojęciem jest rozwinięcie wielomianu , co oznacza, że funkcja f używana do ograniczania gęstości krawędzi płytkich nieletnich jest wielomianem . Jeśli dziedziczna rodzina grafów jest zgodna z twierdzeniem o separatorze , stwierdzającym, że każdy graf n -wierzchołkowy w rodzinie może zostać podzielony na części z co najwyżej n /2 wierzchołkami przez usunięcie O ( n c ) wierzchołków dla pewnej stałej c < 1 , to ta rodzina z konieczności ma wielomianową ekspansję. I odwrotnie, grafy z rozwinięciem wielomianowym mają twierdzenia o separatorze podliniowym.
Klasy grafów z rozwinięciem ograniczonym
Ze względu na związek między separatorami a rozwinięciem, każda rodzina grafów mniejszych domkniętych , w tym rodzina grafów planarnych , ma rozwinięcie wielomianowe. To samo dotyczy grafów 1-planarnych , a ogólniej grafów, które można osadzać na powierzchniach ograniczonego rodzaju z ograniczoną liczbą przejść na krawędź, a także grafów strunowych bez biclique-free , ponieważ wszystkie one są zgodne z podobnymi twierdzeniami o separatorze do grafów planarnych. W większych wymiarów euklidesowych , wykresy przecięcia systemów kulek z własności, że każdy punkt powierzchni jest przykryta przez wiele ograniczonym kulek wypełniać również twierdzeń separatora sugerują wielomianu ekspansji.
Chociaż wykresy ograniczonej grubości książki nie mają separatorów podliniowych, mają również ograniczone rozwinięcie. Inne grafy ograniczonej ekspansji obejmują grafy ograniczonego stopnia, losowe grafy ograniczonego średniego stopnia w modelu Erdősa-Rényiego oraz grafy ograniczonej liczby kolejki .
Aplikacje algorytmiczne
Przypadki problemu izomorfizmu podgrafu, w którym celem jest znalezienie grafu docelowego o ograniczonym rozmiarze, jako podgrafu większego grafu, którego rozmiar nie jest ograniczony, można rozwiązać w czasie liniowym, gdy większy graf należy do rodziny grafów ograniczona ekspansja. To samo dotyczy znajdowania klik o ustalonym rozmiarze, znajdowania dominujących zbiorów o ustalonym rozmiarze lub ogólniej testowania właściwości, które można wyrazić za pomocą formuły o ograniczonym rozmiarze w logice pierwszego rzędu grafów .
Na wykresach wielomianu ekspansji istnieją schematy aproksymacji wielomianem czasie do problemu zestaw pokrywy , maksymalny błąd niezależny zestaw , zbiór dominujący problemem , i kilka innych związanych z tym problemów optymalizacyjnych wykres.