※ 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

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

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

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

元の最小頂点被覆問題を定式化する． $v$ が $S$ に含まれているならば， $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$ .

この整数計画問題の行列はTotally Unimodular Matrixなので，線形計画問題として解くことが出来る（証明略）．以降，線形計画問題として扱う．

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

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$ とする．すると，

流れ込む量 = 流れ出る量なので， $\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$ .

同じ式が得られた．