Nieblokujący

Białe zestawy wierzchołków są maksymalnymi nieblokującymi

W teorii grafów nonblocker jest podzbiorem wierzchołków w grafie nieskierowanym , z których wszystkie sąsiadują z wierzchołkami spoza podzbioru. Równoważnie, nonblocker jest uzupełnieniem zestawu dominującego .

Obliczeniowy problem znalezienia największego elementu nieblokującego na grafie został sformułowany przez Papadimitriou i Yannakakisa (1991) , którzy zauważyli, że należy on do MaxSNP . Chociaż obliczenie zbioru dominującego nie jest wykonalne przy stałych parametrach przy standardowych założeniach, uzupełniający problem znalezienia elementu nieblokującego o danym rozmiarze jest wykonalny przy stałych parametrach.

W grafach bez izolowanych wierzchołków każdy maksymalny element nieblokujący (taki, do którego nie można dodać więcej wierzchołków) sam jest zbiorem dominującym.

Jądrowanie

Jednym ze sposobów skonstruowania wykonalnego algorytmu o stałych parametrach dla problemu bez blokowania jest użycie kernelizacji , algorytmicznej zasady projektowania, w której algorytm czasu wielomianowego jest używany do zredukowania większej instancji problemu do równoważnej instancji, której rozmiar jest ograniczony przez funkcję parametr. W przypadku problemu nieblokującego wejście do problemu składa się z wykresu $styl wyświetlania k}$$parametru$$ma$ a celem $displaystyle$ ustalenie, czy element nieblokujący z $G}$ lub więcej wierzchołków.

Ten problem ma łatwą kernelizację, która redukuje go do równoważnego problemu z co najwyżej wierzchołkami ${\ displaystyle 2k} .$ Najpierw usuń wszystkie izolowane wierzchołki z $.$ ponieważ nie mogą one być częścią żadnego elementu nieblokującego Po wykonaniu tej czynności pozostały graf musi mieć element nieblokujący, który obejmuje co najmniej połowę jego wierzchołków; na przykład, jeśli jedno 2-kolorowe drzewo rozpinające grafu, każda klasa kolorów jest nieblokująca, a jedna z dwóch klas kolorów obejmuje co najmniej połowę wierzchołków. Dlatego jeśli graf z usuniętymi izolowanymi wierzchołkami nadal ma ${\ displaystyle 2k}$ lub więcej wierzchołków, problem można rozwiązać natychmiast. W przeciwnym razie pozostały wykres jest jądrem z co najwyżej ${\ displaystyle 2k}$ .

Dehne i in. ulepszyłem to do jądra o rozmiarze najwyżej ${\ displaystyle {\ tfrac {5} {3}} k + 3}$ . Ich metoda polega na łączeniu par sąsiadów wierzchołków stopnia pierwszego, aż wszystkie takie wierzchołki będą miały jednego sąsiada, i usunięciu wszystkich wierzchołków stopnia pierwszego z wyjątkiem jednego, pozostawiając równoważną instancję z tylko jednym wierzchołkiem stopnia pierwszego. Następnie pokazują, że (z wyjątkiem małych wartości ${$ które można obsługiwać osobno) ta instancja musi być mniejsza niż ograniczenie rozmiaru jądra lub zawierać k $displaystyle k}$ -bloker wierzchołków.

Po uzyskaniu małego jądra, przypadek problemu braku blokowania można rozwiązać w możliwym do opanowania czasie o ustalonych parametrach, stosując algorytm wyszukiwania metodą brute-force do jądra. Zastosowanie szybszych (ale wciąż wykładniczych) granic czasowych prowadzi do ograniczenia czasowego dla problemu bez blokowania w postaci $}$ ) Dla niektórych specjalnych klas grafów możliwe są jeszcze szybsze algorytmy.

Zobacz też

• Zestaw dominujący - uzupełnienie nonblockera.