buyoh.hateblo.jp

残念な競技プログラミング参加者

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

読み返してみて,なんだか読みにくい……後日追記・修正するかもしれません.

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

こんな感じの問題.

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

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

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

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

計算機理論の勉強をする時に,NP完全の1つとして頂点被覆問題の例を挙げることが多いです.

競プロで役に立つの?

出題しました.

No.479 頂点は要らない - yukicoder

ネタばれが嫌いな人は先に解きましょう.

ナップサック問題と同様に,制約によって解き方が変わるので,トレーニングにはなるかな?

一般的なケース

NP困難.厳密解を多項式時間で求めるのは絶望的.

この場合,近似アルゴリズムでなんとかすることが多いようです. 近似アルゴリズムについては既に別館ブログで書きました

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

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

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

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

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

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

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

詳しい解説はyukicoderの解説に載せてあります.

TODO: もう少し詳しく書く

    // 一番高価な頂点からループ
    for (int i = n-1; 0 <= i; --i){
        // もし頂点に接続する辺のうち1つでも一方の頂点が選択されないかつ探索済みであるならば
        // その頂点は選択されるべき
        for (int to : graph.vertex_to[i]){
            if (i < to && !deleted[to]){
                deleted[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);
}

ちゃんとverifyしてません.WAなケースがあったら申し訳ないです.

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

蟻本に書いてあるということもあり,既に多くの方がブログに証明を掲載されているので,いくつか紹介します.

このような条件下のdinic法はオーダーの視点から見ても非常に高速に動作するらしいです.

2部グラフのケース

2部グラフのケースの話に入る前に,頂点被覆を換言しておきます.

頂点集合Sに接続する辺を全て削除したとき,辺が1つも残らない.

最小カットに帰着させるとうまくいきます.

s を源,t を流し台とするフローFを描いてみます.ただし,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

このフローの最小カットを求めるアルゴリズムを走らせると,inf以外の辺をカットしようとします.

辺をカットする操作は,辺に対応する頂点を集合Sに加える操作と同じ意味があります.

よって,このフローの最小カットが,最小頂点被覆のコストです.

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

なぜ辺をカットする操作が,辺に対応する頂点を集合Sに加える操作と同じになるのでしょうか.

a \in Aについて,s\rightarrow aの辺をカットしたとします. aの入次数は1であり,その唯一の辺をカットしたので,頂点aに流れ込む水はありません.

b \in Bについて,b\rightarrow tの辺をカットした場合も同様です. bの出次数は1であり,その唯一の辺をカットしたので,頂点bに流れ込んだとしても流れ出る先がありません.

流量が0な辺は存在しないものとみなせます.よって,次の2つのF'は全く同じグラフです.

  • 2部グラフGから頂点vと接続する辺を取り除いたグラフG'を作ってから,G'のフローグラフF'を作る.
  • 2部グラフGのフローグラフFを作ってから,有向辺(s,v)あるいは(v,t)をカット,流量0の辺と頂点を全て削除したフローグラフF'

以上により,最小カットで解くことができることを説明した気分です.


どうやら,最大独立集合も同じ雰囲気で解けるらしいです. 頂点被覆の補集合は独立集合ですし,無関係ではなさそうです.


2017/06/23追記: きちんと証明する場合,双対定理を用いた方が良さそう?

なんでこんな記事書いたの?

yukicoderの作問没ネタです.

画像描いちゃったし,消すのがもったいなかったので.