Maksymalny niezależny algorytm setu

Question

Nie sądzę, że istnieje algorytm znajdowania maksymalnego niezależnego zestawu wierzchołków na wykresie dwustronnym, inny niż metoda brute force znajdowania maksimum spośród wszystkich możliwych zestawów niezależnych.

Zastanawiam się nad pseudokodami, aby znaleźć wszystkie możliwe zestawy wierzchołków.

Powiedzmy, że mamy dwudzielny wykres z 4 niebieskimi wierzchołkami i 4 czerwonymi. Obecnie chciałbym

Start with an arbitrary blue, 
    find all red that don't match this blue 
    put all these red in Independent Set 
    find all blue that dont match these red 
    put these blue in Independent Set 
    Repeat for next vertex in blue 

Repeat all over again for all blue then all vertices in red. 

Rozumiem, że w ten sposób nie daje mi wszystkie możliwe kombinacje niezależnego zestawu w ogóle, ponieważ po pierwszym etapie mam wyboru wszystkich następnych kolorów wierzchołków że dont mecz zamiast intensyfikacji przez każdy possiblity.

Na przykład biorąc pod uwagę wykres z pasującym

B R 
1 1 
1 3 
2 1 
2 3 
3 1 
3 3 
4 2 
4 4 

Start with blue 1 
    Choose red 2 and 4 since they dont match 
    Add 2, 4 to independent Set 
    Choose 2 and 3 from blue since they dont with 2 or 4 from red 
    Add 2 and 3 from blue to independent set as well. 
Independent Set = 1,2,3 from blue 2,4 from red 
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set) 

Czy istnieje sposób mogę poprawić ten algorytm do lepszego poszukiwaniu wszystkich możliwości. Wiem, że | Maksymalny zestaw dla wykresu dwudzielnego | = | Czerwony | + | Niebieski | - Maksymalne dopasowanie |.

Problem powstaje z możliwością, że wybierając wszystkie możliwe czerwone w pierwszym przejściu dla danego niebieskiego, jeśli te czerwone łączą się ze wszystkimi innymi możliwymi niebieskimi, to mój zestaw ma tylko 1 niebieski i czerwony.

Answer 1

nie wierzę, istnieje algorytm do znalezienia maksymalnej niezależny zbiór wierzchołków w graf dwudzielny innej niż metoda brute force znalezienia maksimum spośród wszystkich możliwych niezależnych zestawów.

Jest: znalezienie maksymalnej niezależnego zestawu jest równoznaczne ze znalezieniem minimalną osłonę wierzchołków (poprzez uzupełnienie wyniku), a Konig's theorem stanowi, że minimalna pokrywa wierzchołek w graf dwudzielny odpowiada maksymalnej dopasowania, oraz że można znaleźć w czasie wielomianowym. Nie wiem, jak znaleźć wszystkie powiązania, ale wydaje się, że może być wykładniczo wiele.

Answer 2

Jak wspomina Aaron McDaid w swojej usuniętej odpowiedzi, problem znalezienia maksymalnego niezależnego zestawu jest równoważny ze znalezieniem maksymalnej kliki. Równoważność polega na tym, że znalezienie maksymalnego niezależnego zbioru na wykresie G jest takie samo jak znalezienie maksymalnej kliki w uzupełnieniu G. Problem jest znany jako NP-zupełny.

Wymienione przez ciebie brute force zajmuje O(n^2 2^n), ale możesz zrobić to lepiej. Robson opublikował artykuł zatytułowany "Algorytmy dla maksymalnych niezależnych zestawów" z 1986 roku, który podaje algorytm, który przyjmuje O(2^{c*n}) dla stałej wartości 0<c<1 (uważam, że c jest około 1/4, ale mógłbym się mylić) .Niektóre z nich jest specyficzne dla wykresu dwudzielnego .

Jedną rzeczą, aby pamiętać, jeśli masz graf dwudzielny jest to, że po obu stronach tworzy niezależny zestaw. w kompletnej graf dwudzielny K_{b,r} który podzielono B x R z |B|=b i |R|=r gdzie istnieje krawędź z każdego wierzchołka w B aby każdy wierzchołek w R i żaden w obrębie B ani żaden w obrębie R, maksymalny niezależny zestaw to B if b>=r, w przeciwnym razie jest to R.

Wykonywanie lub R nie będzie działać w ogóle.sdcvvc zanotował przykład z wierzchołkami {1,2,3,A,B,C} i krawędziami {A,1}, {A,2}, {A,3}, {B,3}, {C,3}. W tym przypadku maksymalny niezależny zestaw to {1,2,B,C}, który jest większy niż każda z partycji {A,B,C} lub {1,2,3}.

Może to poprawić algorytm Robsona, aby zacząć od większego z B lub R i przejść od tego miejsca, choć nie jestem pewien, jak wielką różnicę to zrobi.

Można również użyć Hopcroft–Karp algorithm na dwustronnym dopełnieniu wykresu, aby znaleźć maksymalne dopasowanie, a następnie wziąć wierzchołki użyte w dopasowaniu jako zestaw niezależny. Daje to algorytm wielomianowy do rozwiązania problemu.