一般に、グラフの最大独立サブセットを見つけることは NP ハードです。
ただし、次のグラフのサブセットを検討してください。
単位正方形セルの NxN グリッドを作成します。
すべてのセルに対応する頂点を作成して、グラフ G を作成します。N^2 個の頂点があることに注意してください。
セルが辺を共有している場合、2 つの頂点間にエッジを作成します。2N(N-1) 個のエッジがあることに注意してください。
G の最大独立サブセットは明らかにチェッカー パターンです。R+C が奇数の場合、R 番目の行と C 番目の列のセルはその一部です。
ここで、G をコピーし、いくつかの頂点とエッジを削除して、グラフ G' を作成します。(頂点を削除すると、もちろんそれが終了したすべてのエッジも削除されます。また、終了する頂点のいずれかを削除せずにエッジを削除できることに注意してください。)
G' の最大独立サブセットを見つけるには、どのアルゴリズムを使用しますか?