buyoh.hateblo.jp

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

多項式時間で計算できる最小頂点被覆問題(最小点カバー)について

※ 2017/12/11更新:指数時間アルゴリズムについて記述

※ 2018/02/21更新:全体的に書き直し

最小頂点被覆問題ってなんぞ?

辺集合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完全の1つとして頂点被覆問題の例を挙げることが多いです.

一般的なケース

NP困難.厳密解を多項式時間で求めるのは絶望的であると考えられています.

※ 2017/12/11更新

多項式時間で求められるケース

多項式時間で計算できるケースがいくつか存在します.

各頂点の重みが超増加列である場合

各頂点の重みが超増加列である場合,次が成立します.

  • 『最も高価な頂点のコスト』 は 『最も高価な頂点を除く全ての頂点のコストの総和』 よりも大きい.

最もコストが高い頂点から順にその頂点が必要かどうか判定すればよいです.

頂点が必要かどうかの判定は,その頂点次数に比例する計算量が掛かりますが,全体を数え上げると辺の数の2倍であることが証明できます. よって各頂点の重みがソート済みであるとき,辺の数に比例する線形時間で解を求めることができます.

    // 頂点番号は重みの昇順に割り当てられているものとする
    // 一番高価な頂点からループ
    for (int i = n-1; 0 <= i; --i){
        // もし頂点に接続する辺のうち 1つでも一方の頂点が選択されない かつ 探索済みである ならば
        // その頂点は選択されるべき
        for (int to : graph.vertex_to[i]){ // iに隣接する頂点のそれぞれをtoに代入
            if (i < to && !selected[to]){ // 
                selected[i] = true;
                break;
            }
        }
    }

木構造

グラフが木構造であるということは,閉路が存在しないことを意味します.

頂点を1つ選択してその頂点の状態(Sに含まれるかどうか)を固定すると,複数の木の問題に分割できます.

加えて,メモ化再帰を使うことで線形時間まで計算量を落とせます.

ll dp[100010][2];
ll dfs(int index = 0, int from = -1, bool needed = false) {
    
    // 頂点indexをSに絶対含まなければならない時, needed=true
    
    bool terminal = true;
    
    // メモ化再帰
    if (dp[index][needed]){
        return dp[index][needed];
    }
    
    // 頂点indexをSに含む場合
    ll cost1 = ww[index];
    for (int to : graph.vertex_to[index]) {
        if (to == from) continue;
        terminal = false;
        cost1 += dfs(to, index, false);
    }
    
    if (terminal)
        return dp[index][needed] = (needed ? ww[index] : 0);
    if (needed)
        return dp[index][needed] = cost1;
    
    // 頂点indexをSに含まない場合
    ll cost2 = 0;
    for (int to : graph.vertex_to[index]) {
        if (to == from) continue;
        cost2 += dfs(to, index, true);
    }
    
    return dp[index][needed] = min(cost1, cost2);
}

2部グラフ且つ全ての頂点のWeightが等しいケース

省略

2部グラフのケース

2018/02/21 最小カットで説明していましたが,最大フローに変更し,証明を追記しました.

最大フローに帰着させるとうまくいきます.

s をソース,t をシンクとする有向グラフを描いてみます.ただし,V-A=B, E(A)=\emptyset, E(B)=\emptysetです.

  • a \in A について,a のコストを容量とする s \rightarrow a の有向辺を張る
  • b \in B について,b のコストを容量とする b \rightarrow t の有向辺を張る
  • a,b 間に辺が存在するならば,容量無限大の a \rightarrow b の有向辺を張る

https://drive.google.com/uc?export=view&id=0Bw7ZcbbrTxkzQ25MUi13eTZMeUE

このグラフの最大フローを求めるアルゴリズムを走らせると流量が得られますが,この値は元の最小頂点被覆のコストと一致します.

証明

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

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

この整数計画問題の行列は完全ユニモジュラ行列なので,線形計画問題として解くことが出来る(証明略). 以降,線形計画問題として扱う.

この線形計画問題の双対問題を考えると,

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

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

# # #

さきほど挙げた,有向グラフの最大フロー問題を定式化する. 元のグラフと区別するため,有向グラフを H とし,その辺集合を F\supset E とする.

e に流れる流量を t_e とする.

ソースに隣接する頂点の1つに注目し,v とする.すると,

  • 1つの入口を持ち,その容量は w_v である.
  • 複数の出口の容量に上限は無く,流れ出る量は  \sum_{e \in \delta_G(v)} t_e である.

流れ込む量 = 流れ出る量なので, \sum_{e \in \delta_G(v)} t_e \le w_v

シンクに隣接する頂点も同様に考えることが出来る(略).

以上の考察を用いて,有向グラフの最大フロー問題を定式化すると,

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

同じ式が得られた.