Cześć, czy istnieje jakiś wielomianowy algorytm (albo jakikolwiek, bo to interesująca dla mnie kwestia) wyznaczający maksymalny podgraf dwudzielny w grafie? Zakładając że mamy 1000 wierzchołków, chciałbym wyznaczyć maksymalny podgraf dwudzielny, który może zawierać 27, albo 991 wierzchołków, nieważne, ale istotne że nie będzie większego.
0
1
Google mówią, że się nie da poza specjalnie wybranymi gatunkami grafów
In this paper we present efficient polynomial algorithms for finding a maximum bipartite subgraph for special classes of graphs. In general this problem is NP-complete, and it remains NP-complete even when the graph is restricted to be planar. However, putting further restrictions on the graph makes this problem tractable
Zajrzałem jeszcze do "Computers and Interactibility - A Guide to the theory of NP-Completness" autorstwa Garey'a i Johnsona, książki znanej z encyklopedycznego listowania problemów NP-zupełnych. Interesujący nas fragment:
Jak widać, nawet stwierdzenie, czy dla danego grafu w ogóle można wyznaczyć taki podraf jest NP-zupełne. Perspektywy na algorytmy aproksymacyjne, z tego co widzę, wyglądają biednie.
Nie wiem, czy coś to pomoże, ale zbliżony problem polegający na zrobieniu grafu dwudzielnego poprzez usuwanie krawędzi, a nie wierzchołków jest prostszy:
Tutaj na przykład udało się wygrzebać algorytm aproksymacyjny
0
Co do pytania, czy istnieje jakikolwiek algorytm, to chyba widac że istnieje, starczy przejrzeć każdy podgraf.
0
@Spearhead: Właściwie to chciałbym podzielić graf na jak najmniej podgrafów dwudzielnych. Moją pierwszą myślą było szukanie jak największych do momentu gdy |V| będzie równa 0.
@enedil: No tak, też od razu przyszło mi do głowy sprawdzenie wszystkich podzbiorów
0
samoloth napisał(a):
@Spearhead: Właściwie to chciałbym podzielić graf na jak najmniej podgrafów dwudzielnych. Moją pierwszą myślą było szukanie jak największych do momentu gdy |V| będzie równa 0.
Jeżeli miałbyś algorytm, który dzieli graf na dwa grafy dwudzielne (już nawet pomijając dodatkowe warunki, żeby jeden z nich był jak największy) to mógłbyś go użyć do rozwiązania powyżej opisanego problemu NP-zupełnego sprawdzania czy graf ma indukowany grad dwudzielny (po prostu odrzucając ów drugi podgraf), zatem siłą rzeczy taki algorytm też musi być NP-zupełny.
0
Graf niekoniecznie musiałby być podzielony na dwa grafy dwudzielne. Może to być dowolna ilość, ale możliwie najmniejsza. Domyślam się jednak, że takie założenie nie ma zbyt dużego wpływu na złożoność obliczeniową tego problemu.