buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

最小頂点被覆問題(minimum Vertex Cover)の近似アルゴリズムの実装(draft)

1年前に同様のタイトルで記事を書きましたが,書き直します.

最小頂点被覆問題?

辺集合E,頂点集合Vから成るグラフGが与えられる.
頂点集合S⊆Vを考える.
全ての辺e∈Eが,Sに含まれる頂点に接続している時,SはグラフGの頂点被覆と呼ぶ.

集合Sの大きさが最小であるようなグラフGの頂点被覆Sを1つ求めてください.

頂点集合に重みw:V \rightarrow \mathbb{Q}^+が割り当てられている場合があります. この場合,\sum_{v \in S}w(v)を最小化します.

また,この記事では,『与えられたグラフは単純グラフである』と仮定します.

複雑性

一般的にNP困難.

最適解を求めるアルゴリズム

近似アルゴリズムとは

最適解を求めるアルゴリズムは指数時間アルゴリズムしか知られていないため,大きな入力が与えられると現実的な時間で計算が終わらない可能性がある. そこで,最適解を求める事を諦め,最適に近い実行可能解を求めるアルゴリズムを設計したい. 近似アルゴリズム - Wikipedia

近似アルゴリズムは2種類

近似アルゴリズムは2種類に分類することができる.

  1. 多項式時間で終了し,解を出力するアルゴリズム
  2. 制限時間内ずっと動作し続けるアルゴリズム(焼きなまし).

近似アルゴリズムの評価方法について

次の3つが考えられる.最悪ケースのみを考慮する事もあれば,最悪ケースを考慮しないこともある(例:クイックソート).

  1. 計算時間
  2. 近似精度
  3. 収束速度(焼きなまし)

この記事では厳格な計算は避けて,ゆるふわに解析します.

最小頂点被覆問題の近似アルゴリズムの実装

アルゴリズムその1

次数が大きな頂点を優先的に選択するアルゴリズム

def 最小頂点被覆問題の近似アルゴリズム1:
    入力:無向グラフG=(V,E)
    S := ∅
    while Gは辺を持つ:
        v := (V-S の中で最も次数が大きな頂点を1つ選ぶ)
        S := S ∩ {v}
        グラフGからvとvに接続する辺を削除
    return S

以下の説明では,頂点数N,辺数Mとします.

最悪計算時間

O(N(N+M)).グラフG(V-S)の各頂点の次数を計算する操作でO(E),最も次数が大きな頂点を探す操作でO(N). whileループ内部の中はO(N+M).入力グラフがクリークの時,最大でN-1個の頂点が選択されるので,ループ回数はO(N).全体でO(N(N+M)).

ただし,頂点次数計算を予め計算しておき,頂点を削除するごとに更新するアルゴリズムに変更すれば,O(N2)に抑えられる.

近似精度

得られる近似解の大きさが最適解の(1+lnM)倍で収まるらしい.

本記事では,得られる近似解の大きさが最適解の定数倍で収まらない入力ケース*1が存在することを証明します.

6以上の高度合成数 K を適当に決める.K=\prod_{i=1}^{L} p_i^{l_i} という形で素因数分解しておく.p_i素数

K 個の頂点集合 A と,K/p_1 個の頂点集合B_1K/p_2 個の頂点集合 B_2,・・・, K/p_L 個の頂点集合 B_L を作る.

i \in \{1..L\}j \in \{1..K/p_1\} について,次の操作に従って辺を引いていく.

  •  B_i に属する j 番目の頂点と,A に属する  (j-1)p_i+1 番目から  jp_i 番目の頂点を辺で接続する.

出来上がるグラフは,2部グラフの形になる.グラフ G と命名しておく.

G の最小頂点被覆の最適解は,Aとなる.しかし,上で示した近似アルゴリズムは,調子が悪いと \bigcup B_i を全て選択する. |A|=K|\bigcup B_i|=\sum_{i=1}^{L}\ p_i^{l_i} なので,近似率は \frac{\sum_{i=1}^{L}\ p_i^{l_i}}{K} となる.

\sum_{i=1}^{L}\ p_i^{l_i} とは K の約数の総和なので,だいたいΘ(KlnlnK)である?2018/05/06修正*2
よって,近似率は Ω(lnlnK) となり,得られる近似解の大きさが最適解の定数倍で収まらない入力ケースが存在する.

アルゴリズムその2

まず,最小頂点被覆問題を整数計画問題に定式化する.  vS に含まれているならば,s_v=1 ,含まれていないならば s_v=0 と定義して定式化すると,

minimize  \sum_{v \in V} s_i
subject to  s_u+s_v \ge 1 , \{u,v\} \in E.

この整数計画問題を線形計画問題として解く

得られる解は整数とは限らないが,その場合は小数点以下を切り上げたものを近似解とする.

最悪計算時間

線形計画問題ソルバのお気持ち.

最悪近似精度

得られる近似解の大きさが最適解の2倍以内で収まる.以下証明.

双対定理より,双対問題を設計する.

maximize  \sum_{e \in E} t_e
subject to  \sum_{e \in \delta_G(v)} t_e \le 1 , v \in V.

ただし,関数 \delta_G :V \rightarrow 2^E, \delta (v) は,グラフ G において v に接続する辺集合を表す.

相補条件(主問題と双対問題の目的関数が最適解であるための条件)は,

s_v = 0 または \sum_{\delta(v)} t_e = 1, v \in V
t_e = 0 または s_{u} + s_{v} = 1, \{u,v\} = e, e \in E.

相補条件を緩和する.

s_v = 0 または \frac{1}{\alpha} \le \sum_{\delta(v)} t_e \le 1, v \in V
t_e = 0 または 1 \le s_{u} + s_{v} \le \beta, \{u,v\} = e, e \in E.

Primal-Dual法より,緩和相補条件を満足する解が得られた時,近似解は最適解の \alpha\beta 倍で抑えられる.

[tex;\alpha]と[tex;\beta]が何か調べるため,設計したアルゴリズムに戻って確認してみると,主問題のLPを求めた後,主問題の解を切り上げている. 双対問題は緩和していない(何も手を加えていない)事から,

s_v = 0 または \sum_{\delta(v)} t_e = 1, v \in V
t_e = 0 または 1 \le s_{u} + s_{v} \le 2, \{u,v\} = e, e \in E.

\alpha=1\beta=2 より,近似解は最適解の 2 倍で抑えられる

アルゴリズムその3

def 最小頂点被覆問題の近似アルゴリズム2:
    入力:無向グラフG=(V,E)
    p := 要素数|V|の配列.1で初期化.
    for e := E:
        t := min(p_u,p_v)
        p_u := p_u - t
        p_v := p_v - t
    return { i | p_i =0 }

最悪計算時間

O(N+M).

最悪近似精度

得られる近似解の大きさが最適解の2倍以内で収まる

for ループ中で e を取り出している時の t の値を t_e と書くことにする.

上のアルゴリズムは,次のLPを単体法で解いているだけである.

maximize  \sum_{e \in E} t_e
subject to  \sum_{e \in \delta_G(v)} t_e + p_v = 1 , v \in V.

p_v をスラック変数として解釈すれば,最小頂点被覆問題のLP緩和の双対問題と一致する.

アルゴリズム2と似た議論をすれば2倍近似が示せる.(TODO: )

参考資料

  • Design and Analysis of Application Algorithms

*1:最悪ケースではない

*2:実際に計算した.https://ideone.com/Q4yzQ1 .証明にはなっていないが大筋Θ(KlnlnK)の気がする.要証明.