Algorytmy aproksymacji dla maksymalnego niezależnego zestawu na specjalnych klasach wykresów

Wiemy, że maksymalny niezależny zestaw (MIS) jest trudny do przybliżenia przy współczynniku dla dowolnego ϵ > 0, chyba że P = NP. Jakie są specjalne klasy wykresów, dla których znane są lepsze algorytmy aproksymacyjne?$n^{1-\epsilon}$$\epsilon > 0$

Jakie są wykresy, dla których znane są algorytmy wielomianowe? Wiem, że dla idealnych wykresów jest to znane, ale czy istnieją inne ciekawe klasy wykresów?

Istnieje naprawdę niesamowita lista wszystkich znanych klas grafów, które mają nietrywialne algorytmy dla MIS: zobacz ten wpis na stronie klas grafów.

Nie mam dobrego przeglądu tego problemu, ale mogę podać kilka przykładów. Prostym algorytmem aproksymacyjnym byłoby znalezienie pewnej kolejności węzłów i chciwe wybranie węzłów, które mają znajdować się w niezależnym zestawie, jeśli nie wybrano żadnego z jego poprzednich sąsiadów w niezależnym zestawie.

Jeśli wykres ma zwyrodnienie wówczas zastosowanie kolejności zwyrodnienia da przybliżenie d . stąd dla wykresów degeneracji n 1 - ϵ mamy wystarczająco dobre przybliżenie.$d$$d$$n^{1-\epsilon}$

Istnieje kilka innych technik przybliżania, które również działają, ale nie znam ich dobrze. Zobacz: http://en.wikipedia.org/wiki/Baker%27s_technique i http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf

Do algorytmów wielomianowych dokładnie rozwiązujących problemy Link podany przez Suresha jest najlepszy. Trudno powiedzieć, które klasy graficzne są bardziej interesujące.

Jedną klasą, której nie znajdziesz na tej liście, jest uzupełnienie wykresów degenerujących. Ponieważ maksymalną klikę można rozwiązać w O ( 2 tys. N ) na wykresach zwyrodnienia k patrz http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorytm, szczególnie dzieło Eppsteina. Wtedy zestaw niezależny jest wielomianem na G, jeśli uzupełnienie G ma degenerację O ( log n ) .$k$$O(2^k n)$$k$$O(\log n)$

W przypadku klasy sześciennych grafów płaskich ten dokument, Algorytm aproksymacji dla problemu maksymalnego niezależnego zestawu w sześciennych grafach płaskich autorstwa Elarbiego Choukhmane i Johna Franco, podaje algorytm wielomianowego aproksymacji czasu. Współczynnik aproksymacji ich algorytmu wynosi 6/7.

Nie sprawdziłem odpowiedzi powyżej, więc przepraszam, jeśli się pokrywają. Oto szczególny przypadek, w którym możesz rozwiązać go dokładnie w czasie wielomianowym. Jeśli wykres G jest wykresem liniowym , uruchom algorytm wielomianu czasu , aby znaleźć wykres główny H, a następnie znajdź maksymalne dopasowanie w H.

Na geometrycznych wykresach przecięcia istnieje kilka interesujących przybliżeń, PTAS i dokładnych algorytmów sub wykładniczych. Zobacz artykuł w Wikipedii Maximum Disjoint Set dla ankiety.