Znajdź cały maksymalny kompletny, dwudzielny subgraph z danego dwudzielnego wykresu

Question

Podany jest dwustronny wykres, a my chcemy wyświetlić cały maksymalny pełny dwuartydzielny pod-wykres.

Przykładowo

zbiór wierzchołków L = {A, B, C, D,}

zestaw wierzchołek R = {a, b, c, d, e}

krawędzie AA Ab, BA, BB, Cc, Cd, DC, dd, De

maksymalna zakończeniu dwustronnego są:

{A, b} - {A, b}

{C, D,} - {c, d}

{D} - {c, d, e}

I znaleziono algorytm brute force, O (2^N). Nie wiem, czy jakiś algorytm aproksymacyjny lub algorytm randomizowany.

Answer 1

Możesz zmienić problem, aby znaleźć maksymalne kliknięcia, dodając krawędzie między każdą parą wierzchołków w każdej części wykresu dwudzielnego.

Algorytm Bron-Kerboscha może być użyty do wyświetlenia wszystkich maksymalnych klik na wykresie (niekoniecznie dwudzielnym). Jest dość łatwy w implementacji i ma nieco lepszy najgorszy możliwy czas związany z O (3^(n/3)). Istnieje również stały czas parametru fix-fix związany z degeneracją wykresu.