Niezależny zbiór (teoria grafów) - Independent set (graph theory)

Dziewięć niebieskich wierzchołków tworzy maksymalny niezależny zbiór dla uogólnionego grafu Petersena GP(12,4).

W teorii wykres , na niezależnym zbiorze , stabilnej zestawu , coclique lub anticlique to zbiór wierzchołków na wykresie , nie dwa, które sąsiadują ze sobą. Oznacza to, że jest to zbiór wierzchołków taki, że na każde dwa wierzchołki w , nie ma krawędzi łączącej te dwa. Równoważnie każda krawędź na wykresie ma co najwyżej jeden punkt końcowy w . Zbiór jest niezależny wtedy i tylko wtedy, gdy jest kliką w dopełnieniu grafu . Rozmiar niezależnego zestawu to liczba wierzchołków, które zawiera. Zbiory niezależne nazwano także „zbiorami wewnętrznie stabilnymi”, których skrótem jest „zbiór stabilny”. ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

Maksymalny niezależny zestaw jest niezależną zestaw, który nie jest właściwy podzbiór jakiegokolwiek innego niezależnego zestawu.

Maksymalna niezależny zestaw jest niezależny zestaw możliwie największych rozmiarach dla danego wykresu . Rozmiar ten jest nazywany numer niezależność od i jest zazwyczaj oznaczona . Problem optymalizacji znalezienia takiego zestawu jest nazywany maksymalny zbiór niezależny problemem. Jest to problem silnie NP-trudny . W związku z tym jest mało prawdopodobne, że istnieje wydajny algorytm znajdowania maksymalnego niezależnego zbioru grafu. ${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle \ alfa (G)}$

Każdy maksymalny niezależny zbiór również jest maksymalny, ale implikacja odwrotna niekoniecznie jest aktualna.

Nieruchomości

Związek z innymi parametrami wykresu

Zbiór jest niezależny wtedy i tylko wtedy, gdy jest kliką w dopełnieniu grafu , więc te dwa pojęcia są komplementarne. W rzeczywistości wystarczająco duże grafy bez dużych klik mają duże niezależne zbiory, co jest tematem badanym w teorii Ramseya .

Zbiór jest niezależny wtedy i tylko wtedy, gdy jego uzupełnieniem jest pokrycie wierzchołka . Dlatego suma wielkości największego niezależnego zbioru i wielkości minimalnego pokrycia wierzchołków jest równa liczbie wierzchołków na wykresie. ${\ Displaystyle \ alfa (G)}$${\ Displaystyle \ beta (G)}$

Wierzchołek barwienia wykresu odpowiada w partycji jej wierzchołka do zestawu niezależnych podzbiorów. Stąd minimalna liczba kolorów potrzebnych do kolorowania wierzchołków, liczba chromatyczna , jest co najmniej ilorazem liczby wierzchołków i niezależnej liczby . ${\ Displaystyle G}$ ${\ Displaystyle \ chi (G)}$${\ Displaystyle G}$${\ Displaystyle \ alfa (G)}$

W grafie dwudzielnym bez izolowanych wierzchołków liczba wierzchołków w maksymalnym niezależnym zbiorze jest równa liczbie krawędzi w minimalnym pokryciu krawędzi ; to jest twierdzenie Kőniga .

Maksymalny niezależny zestaw

Niezależny zbiór, który nie jest właściwym podzbiorem innego niezależnego zbioru, nazywa się maximal . Takie zestawy to zestawy dominujące . Każdy wykres zawiera co najwyżej 3 ^{n /3} maksymalnych niezależnych zbiorów, ale wiele wykresów ma ich znacznie mniej. Liczba maksymalnych niezależnych zbiorów w n- wierzchołkowych wykresach cykli jest określona przez liczby Perrina , a liczba maksymalnych niezależnych zbiorów w n- wierzchołkowych grafach ścieżek jest określona przez sekwencję Padovana . Dlatego obie liczby są proporcjonalne do potęg 1.324718..., liczby plastycznej .

Znajdowanie niezależnych zestawów

W informatyce zbadano kilka problemów obliczeniowych związanych z niezależnymi zbiorami.

• W zagadnieniu maksymalnego niezależnego zbioru wejście jest grafem nieskierowanym, a wyjście jest maksymalnym niezależnym zbiorem na grafie. Jeśli istnieje wiele maksymalnych niezależnych zestawów, wystarczy wyprowadzić tylko jeden. Ten problem jest czasami określany jako „ upakowanie wierzchołków ”.
• W zagadnieniu zbioru niezależnego od maksymalnej wagi , wejście jest grafem nieskierowanym z wagami na jego wierzchołkach, a wyjściem jest niezależny zbiór o maksymalnej wadze całkowitej. Problem maksymalnego niezależnego zbioru to szczególny przypadek, w którym wszystkie wagi są jednym.
• W maksymalnym niezależnego zestawu wystawianie problemu, wejście jest nieukierunkowane wykres, a wyjście jest lista wszystkich swoich maksymalnych niezależnych zestawów. Problem maksymalnego niezależnego zbioru można rozwiązać używając jako podprogramu algorytmu dla zadania z listą maksymalnego niezależnego zbioru, ponieważ maksymalny zbiór niezależny musi być zawarty wśród wszystkich maksymalnych zbiorów niezależnych.
• W problemie decyzyjnym dotyczącym niezależnego zbioru dane wejściowe to graf nieskierowany i liczba k , a wyjściem jest wartość logiczna : prawda, jeśli graf zawiera niezależny zbiór o rozmiarze k , a w przeciwnym razie fałsz.

Pierwsze trzy z tych problemów są ważne w zastosowaniach praktycznych; problem decyzji o zbiorach niezależnych nie jest, ale jest konieczny, aby zastosować teorię NP-zupełności do problemów związanych ze zbiorami niezależnymi.

Maksimum niezależnych zestawów i maksimum klik

Problem niezależny zestaw i błąd klika są komplementarne: klika w G jest niezależny zestaw na wykresie dopełniacza z G i na odwrót. Dlatego wiele wyników obliczeniowych może być równie dobrze zastosowanych do obu problemów. Na przykład wyniki związane z problemem kliki mają następujące konsekwencje:

• Niezależny problem decyzyjny zbioru jest NP-zupełny i dlatego nie uważa się, że istnieje skuteczny algorytm do jego rozwiązania.
• Problem maksymalnych zbiorów niezależnych jest NP-trudny i również trudny do aproksymacji .

Pomimo ścisłego związku między maksymalnymi klikami i maksymalnymi niezależnymi zbiorami w arbitralnych grafach, problemy zbiorów niezależnych i klik mogą być bardzo różne, gdy są ograniczone do specjalnych klas grafów. Na przykład w przypadku grafów rzadkich (grafów, w których liczba krawędzi jest co najwyżej stała razy liczba wierzchołków w każdym podgrafie), maksymalna klika ma ograniczony rozmiar i może być znaleziona dokładnie w czasie liniowym; jednak dla tych samych klas grafów, a nawet dla bardziej ograniczonej klasy grafów o ograniczonym stopniu, znalezienie maksymalnego niezależnego zbioru jest MAXSNP-zupełne , co oznacza, że ​​dla pewnej stałej c (w zależności od stopnia) jest to NP-trudne do znaleźć przybliżone rozwiązanie, które mieści się we współczynniku c optimum.

Znajdowanie maksymalnych niezależnych zbiorów

Dokładne algorytmy

Problem maksymalnego niezależnego zbioru jest NP-trudny. Można go jednak rozwiązać wydajniej niż czas O( n ²  2 ⁿ ), który byłby podany przez naiwny algorytm brute force, który bada każdy podzbiór wierzchołków i sprawdza, czy jest to zbiór niezależny.

Od 2017 roku można go rozwiązać w czasie O(1.1996 ⁿ ) za pomocą przestrzeni wielomianowej. Ograniczony do wykresów o maksymalnym stopniu 3, można go rozwiązać w czasie O(1.0836 ⁿ ).

Dla wielu klas grafów, w czasie wielomianowym można znaleźć zbiór niezależnych od maksymalnej wagi. Znani przykłady pazur wolne wykresy , P ₅ -Darmowe wykresy i graf doskonały . W przypadku wykresów akordowych , maksymalny niezależny od ciężaru zbiór można znaleźć w czasie liniowym.

Rozkład modułowy jest dobrym narzędziem do rozwiązania problemu zbiorów niezależnych od maksymalnej wagi; algorytm czasu liniowego na wykresach jest tego podstawowym przykładem. Innym ważnym narzędziem są separatory klików opisane przez Tarjana.

Twierdzenie Kőniga implikuje, że w grafie dwudzielnym maksymalny niezależny zbiór można znaleźć w czasie wielomianowym przy użyciu algorytmu dopasowywania dwudzielnego.

Algorytmy aproksymacyjne

Ogólnie rzecz biorąc, problem maksymalnego niezależnego zbioru nie może być aproksymowany do stałego współczynnika w czasie wielomianu (chyba że P = NP). Ogólnie rzecz biorąc, Max Independent Set to Poly-APX-complete , co oznacza, że ​​jest tak trudny, jak każdy problem, który można przybliżyć do współczynnika wielomianowego. Istnieją jednak wydajne algorytmy aproksymacji dla ograniczonych klas grafów.

W grafach planarnych maksymalny niezależny zbiór może być aproksymowany w dowolnym stosunku aproksymacji c  < 1 w czasie wielomianowym; podobne schematy aproksymacji w czasie wielomianowym istnieją w każdej rodzinie grafów zamkniętych w ramach brania nieletnich .

W grafach ograniczonych stopni znane są efektywne algorytmy aproksymacji ze współczynnikami aproksymacji, które są stałe dla ustalonej wartości maksymalnego stopnia; na przykład zachłanny algorytm, który tworzy maksymalny niezależny zbiór, wybierając na każdym kroku wierzchołek o minimalnym stopniu z grafu i usuwając jego sąsiadów, osiąga stosunek aproksymacji (Δ+2)/3 na grafach o maksymalnym stopniu Δ. Przybliżone granice twardości dla takich przypadków potwierdzili Berman i Karpiński (1999) . Rzeczywiście, nawet Max Independent Set na 3-regularnych 3-krawędziowych wykresach jest kompletny APX .

Niezależne zbiory w grafach przecięcia interwałów

Przedział wykres przedstawia wykres, w którym węzły odstępach 1-wymiarowe (na przykład przedziały czasu), a tam jest krawędź między dwoma odstępach, wtedy i tylko wtedy, gdy się przecinać. Niezależny zbiór na wykresie interwałowym to po prostu zbiór niezachodzących na siebie interwałów. Problem znajdowania maksymalnych niezależnych zbiorów na wykresach interwałowych był badany na przykład w kontekście planowania zadań : mając zbiór zadań, które mają być wykonane na komputerze, znajdź maksymalny zbiór zadań, które mogą być wykonane bez ingerencji ze sobą. Ten problem można rozwiązać dokładnie w czasie wielomianowym, używając pierwszego harmonogramu najwcześniejszego terminu .

Niezależne zbiory w geometrycznych grafach przecięcia

Geometryczny wykres przecięcia to wykres, w którym węzły mają kształty geometryczne, a pomiędzy dwoma kształtami występuje krawędź wtedy i tylko wtedy, gdy się przecinają. Niezależny zbiór w geometrycznym wykresie przecięcia to po prostu zbiór rozłącznych (nie nakładających się) kształtów. Problem znajdowania maksymalnych niezależnych zbiorów w grafach przecięć geometrycznych był badany na przykład w kontekście automatycznego umieszczania etykiet : mając dany zbiór lokalizacji na mapie, znajdź maksymalny zbiór rozłącznych prostokątnych etykiet w pobliżu tych lokalizacji.

Znalezienie maksymalnego zbioru niezależnego w grafach przecięcia jest nadal NP-zupełne, ale jest łatwiejsze do aproksymacji niż ogólny problem maksymalnego zbioru niezależnego. Ostatnie badanie można znaleźć we wstępie Chana i Har-Peleda (2012) .

Znajdowanie maksymalnych niezależnych zbiorów

Problem znalezienia maksymalnego niezależnego zbioru można rozwiązać w czasie wielomianowym za pomocą trywialnego algorytmu zachłannego . Wszystkie maksymalne niezależne zbiory można znaleźć w czasie O(3 ^{n /3} ) = O(1,4423 ⁿ ).

Oprogramowanie do wyszukiwania maksymalnie niezależnego zestawu

Aplikacje

Zbiór maksymalny niezależny i jego dualność, problem minimalnego pokrycia wierzchołków , są zaangażowane w udowodnienie złożoności obliczeniowej wielu problemów teoretycznych. Służą one również jako użyteczne modele dla problemów optymalizacji w świecie rzeczywistym, na przykład minimalny niezależny zbiór jest użytecznym modelem do odkrywania stabilnych komponentów genetycznych do projektowania systemów genetycznych modyfikowanych inżynierią .

Zobacz też

• Niezależny zbiór krawędzi to zbiór krawędzi, z których żadne dwa nie mają wspólnego wierzchołka. Nazywa się to zwykle dopasowaniem .
• Wierzchołek barwiących jest partycja zestawu wierzchołek na niezależne zestawy.

Uwagi

Bibliografia

Zewnętrzne linki

• Weisstein, Eric W. „Maksymalny niezależny zestaw wierzchołków” . MatematykaŚwiat .
• Trudne kryteria dla maksymalnej kliki, maksymalnego niezależnego zestawu, minimalnego pokrycia wierzchołków i kolorowania wierzchołków
• Niezależny zestaw i osłona wierzchołków , Hanan Ayad.