Neblokující - Nonblocker - Wikipedia

Sady bílých vrcholů jsou maximální neblokovače

v teorie grafů, a neblokující je podmnožina vrcholů v neorientovaný graf, které všechny sousedí s vrcholy mimo podmnožinu. Ekvivalentně neblokující je doplněk a dominující sada.^[1]

Výpočtový problém nalezení největšího neblokujícího v grafu byl formulován pomocí Papadimitriou & Yannakakis (1991), který poznamenal, že patří MaxSNP.^[2]Ačkoli výpočet dominující množiny není fixovatelný parametr za standardních předpokladů je doplňkovým problémem nalezení neblokovače dané velikosti traktovatelný s pevnými parametry.^[1]

V grafech bez č izolované vrcholy, každý maximální neblokující (jeden, ke kterému nelze přidat žádné další vrcholy) je sám o sobě dominující množinou.^[3]

Kernelizace

Jedním ze způsobů, jak zkonstruovat traktovatelný algoritmus s pevným parametrem pro problém bez blokování, je použití kernelizace, princip algoritmického návrhu, ve kterém se algoritmus polynomiálního času používá ke zmenšení instance většího problému na ekvivalentní instanci, jejíž velikost je omezena funkcí parametru. U problému bez blokování se vstup do problému skládá z grafu ${ displaystyle G}$ a parametr ${ displaystyle k}$, a cílem je zjistit, zda ${ displaystyle G}$ má neblokovač s ${ displaystyle k}$ nebo více vrcholů.^[1]

Tento problém má snadnou kernelizaci, která jej maximálně snižuje na ekvivalentní problém ${ displaystyle 2k}$ vrcholy. Nejprve odstraňte všechny izolované vrcholy z ${ displaystyle G}$, protože nemohou být součástí žádného neblokovače. Jakmile to bylo provedeno, zbývající graf musí mít neblokovací nástroj, který zahrnuje alespoň polovinu jeho vrcholů; například pokud jeden 2 barvy žádný kostra grafu, každá barevná třída neblokuje a jedna ze dvou barevných tříd zahrnuje alespoň polovinu vrcholů. Pokud tedy graf s odstraněnými izolovanými vrcholy stále existuje ${ displaystyle 2k}$ nebo více vrcholů, problém lze vyřešit okamžitě. Jinak je zbývající graf jádro s maximem ${ displaystyle 2k}$ vrcholy.^[1]

Dehne a kol. vylepšil to maximálně na velikost jádra ${ displaystyle { tfrac {5} {3}} k + 3}$. Jejich metoda zahrnuje slučování dvojic sousedů vrcholů stupně jedna, dokud všechny takové vrcholy nemají jediného souseda, a odstranění všech vrcholů stupně jedna kromě jednoho a ponechání ekvivalentní instance pouze s jedním vrcholem stupně jedna. Poté ukazují, že (až na malé hodnoty ${ displaystyle k}$, které lze zpracovat samostatně) musí být tato instance buď menší než vázaná velikost jádra, nebo musí obsahovat a ${ displaystyle k}$-vertex blocker.^[1]

Jakmile je získáno malé jádro, může být instance problému bez blokování vyřešena ve fixovatelném čase s pevným parametrem aplikací vyhledávání hrubou silou algoritmus jádra. Uplatnění rychlejších (ale stále exponenciálních) časových mezí vede k časově ohraničenému problému neblokujícího formuláře ${ displaystyle O (2,5154 ^ {k} + n)}$. Pro některé speciální třídy grafů jsou možné ještě rychlejší algoritmy.^[1]

Reference