2部グラフ上の重み付き最小点カバー問題を解くアルゴリズム
※ 2017/12/11更新:指数時間アルゴリズムについて記述
※ 2018/02/21更新:全体的に書き直し
※ 2018/11/02更新:2部グラフのケースのみ残し,タイトルを変更.
最小点カバー問題
辺集合E,頂点集合V,頂点重みw(v)から成るグラフGが与えられる. 頂点集合S⊆Vを考える. 全ての辺e∈Eが,Sに含まれる頂点の少なくとも1つに接続している時,SはグラフGの頂点被覆と呼ぶ. 頂点集合Sの重みの総和が最小であるようなグラフGの頂点被覆Sを1つ求めてください.
solve
最大フローに帰着させるとうまくいきます.
をソース, をシンクとする有向グラフを描いてみます.ただし,です.
- について, のコストを容量とする の有向辺を張る
- について, のコストを容量とする の有向辺を張る
- 間に辺が存在するならば,容量無限大の の有向辺を張る
このグラフの最大フローを求めるアルゴリズムを走らせると流量が得られますが,この値は元の最小頂点被覆のコストと一致します.
証明
元の最小頂点被覆問題を定式化する. が に含まれているならば, ,含まれていないならば と定義して定式化すると,
minimize
subject to .
この整数計画問題の行列はTotally Unimodular Matrixなので,線形計画問題として解くことが出来る(証明略). 以降,線形計画問題として扱う.
この線形計画問題の双対問題を考えると,
maximize
subject to .
ただし,関数 は,グラフ G において v に接続する辺集合を表す.
# # #
さきほど挙げた,有向グラフの最大フロー問題を定式化する. 元のグラフと区別するため,有向グラフを とし,その辺集合を とする.
辺 に流れる流量を とする.
ソースに隣接する頂点の1つに注目し, とする.すると,
- 1つの入口を持ち,その容量は である.
- 複数の出口の容量に上限は無く,流れ出る量は である.
流れ込む量 = 流れ出る量
なので,.
シンクに隣接する頂点も同様に考えることが出来る(略).
以上の考察を用いて,有向グラフの最大フロー問題を定式化すると,
maximize
subject to .
同じ式が得られた.