頂点被覆

頂点被覆(vertex cover)とは、あるグラフの点のサブセットであって、全ての辺がその点に接しているものをいう。
最小点被覆とは、点被覆の大きさをできるだけ少なくするもので、一般の場合では(決定問題に"グラフCに大きさk以下の頂点被覆があるか"として変換した場合)NP完全である。
常に、(マッチングに含まれる点の個数 <= 最小点被覆の点の個数) であって、(最小点被覆の点の個数 <= 極大マッチングに含まれる点の個数 * 2)で近似できる。
二部グラフの場合には、"Königの定理"によって、(最大マッチングの点の数 = 最小点被覆の点の数) であることがわかっていて、簡単に解ける。