Algorytm wyliczania kliki

9

Czytam stary artykuł MC Golumbica na temat wykresów EPT (przecięcie krawędzi ścieżek na drzewie). W artykule pokazano, że liczba maksymalnych klików wystąpienia wykresu EPT jest wielomianowa. Stwierdza, że jeśli wyrocznia zgłasza, że wykres $G$ jest wykresem EPT, możliwe jest znalezienie maksymalnej kliki za pomocą standardowego algorytmu wyliczania kliki.

Po pierwsze, jakie są te standardowe algorytmy wyliczania klików? Jeśli istnieje więcej niż jeden, czy możemy powiedzieć, że jeśli liczba maksymalnych klików wykresu jest wielomianowa, to czy możemy zastosować dowolny z tych algorytmów wyliczania? Czy też powinniśmy czerpać specjalny algorytm z algorytmu ogólnego, który wykorzystuje pewne specjalne struktury klasy grafowej?

Z góry dziękuję.

ds.algorithms graph-algorithms clique

— Arman
źródło

13

Istnieje kilka algorytmów wrażliwych na dane wyjściowe do wyliczenia wszystkich maksymalnych klików w czasie wielomianowym na wyjście. Jeden z pierwszych algorytmów został opracowany przez Tsukiyama, Ide, Ariyoshi i Shirakawa (1977).

Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa: Nowy algorytm do generowania wszystkich maksymalnych niezależnych zestawów. SIAM J. Comput. 6 (3): 505–517 (1977)

Oznacza to, że jeśli wiesz, że twój wykres ma co najwyżej wielomianowo wiele maksymalnych klików, wówczas całkowity czas działania ich algorytmu będzie wielomianowy pod względem wielkości wejściowej.

— Yoshio Okamoto
źródło

Niestety nie mam dostępu do gazety. Ale jestem pewien, że tego właśnie szukam, dziękuję.

— Arman,

4

Algorytm Bron-Kerbosch oblicza wszystkie maksymalne kliky na niekierowanym grafie (patrz Wikipeadia ). Najgorszy czas działania to O (3 ^{n / 3} ), najwyraźniej jest on ogólnie bardzo szybki i nadal jest najszybszym znanym algorytmem do obliczania wszystkich maksymalnych klików. Dla nowszych odniesienia zobaczyć papiery V. Stix i Cazals i Karande .

— Volker Turau
źródło

2

Aby uzyskać

O (3^{n / 3})

$O(3^{n/3})$ W związku z tym potrzebujemy małej sztuczki, aby skutecznie wykonywać odgałęzienia w procedurze cofania (z powodu Tomity, Tanaki i Takahashi). Warto również zauważyć, że granica

3^{n / 3}

$3^{n/3}$ jest optymalne w najgorszym przypadku, ponieważ istnieje wykres z

3^{n / 3}

$3^{n/3}$ maksymalne kliky (a mianowicie

K_{3, 3, . . ., 3}

$K_{3,3,...,3}$ ).

— Yoshio Okamoto,

1

Nowsze prace nad Bronem-Kerboschem znajdują się w moich artykułach arxiv.org/abs/1006.5440 z Strash i Löffler na ISAAC 2010 oraz arxiv.org/abs/1103.0318 z Strash na SEA 2011. Jednak tak naprawdę nie odpowiada to na pytanie pierwotnego autora ponieważ algorytm nie jest wrażliwy na dane wyjściowe: może to zająć wykładniczy czas, nawet gdy jest tylko wiele wielomianowo maksymalnych klików.

— David Eppstein,