Nonblocker とは

グラフ理論では、ノンブロッカーは、無向グラフの頂点のサブセットであり、そのすべてがサブセットの外側の頂点に隣接しています。同様に、ノンブロッカーは支配的なセットの補集合です。
グラフ中の最大のノンブロッカーを発見する計算上の問題は、Papadimitriou&Yannakakis(1991)によって定式化され、MaxSNPに属することが観察された。支配的な集合を計算することは、標準的な仮定の下では固定パラメータの取り扱いができないが、与えられたサイズの非ブロックを見つける補完的な問題は、固定パラメータ扱いやすい。
孤立した頂点を持たないグラフでは、すべての最大非ブロッカー(それ以上の頂点を追加できないもの)自体が支配的な集合です。