頂点被覆
最小頂点被覆問題は、与えられたグラフの最小頂点被覆を求める最適化問題である。
INSTANCE: グラフ G
OUTPUT: G の頂点被覆 C の大きさ k について、最小のもの。
決定問題とする場合は、これを頂点被覆問題と呼び、次のように定式化される。
INSTANCE: グラフ G と正の整数 k
QUESTION: G の頂点被覆 C で、その大きさが k 以下のものがあるか?
頂点被覆問題はNP完全問題である。カープの21のNP完全問題の1つになっており、他の問題がNP困難であることを示す手段として計算複雑性理論でよく利用される。
各頂点にはコスト c ( v ) ≥ 0 {\displaystyle c(v)\geq 0} が対応するものとする。(重み付き)最小頂点被覆問題は、次のように整数計画問題として定式化できる。
∑ v ∈ V c ( v ) x v {\displaystyle \sum _{v\in V}c(v)x_{v}} を最小化する(トータルコストを最小化)
このとき、全ての { u , v } ∈ E {\displaystyle \{u,v\}\in E} について x u + x v ≥ 1 {\displaystyle x_{u}+x_{v}\geq 1} であり、(グラフの全ての辺を被覆する)
かつ全ての v ∈ V {\displaystyle v\in V} について x v ∈ { 0 , 1 } {\displaystyle x_{v}\in \{0,1\}} である。(全ての頂点は頂点被覆に含まれるか否かのどちらかである)
この整数計画問題(ILP)は、被覆問題と呼ばれるより大きなILPクラスに属する。このILPの整数性ギャップは 2 であり、その緩和から最小頂点被覆問題に対して係数 2 の近似アルゴリズムが得られる。さらに言えばこのILPの線形計画緩和は half-integral であり、全ての v ∈ V {\displaystyle v\in V} について x v ∈ { 0 , 0.5 , 1 } {\displaystyle x_{v}\in \{0,0.5,1\}} の最適解が存在する。