前回の記事では，競プロ界隈における「燃やす埋める問題」と離散最適化のトピックである「劣モジュラ関数のグラフ表現可能性」の関係性について述べ，与えられた列モジュラ関数が最小カットを通して最小化できるための条件について説明しました．

今回の記事の目的は，実際に問題が与えられたときどのようにグラフを構築すれば良いか，という方法論を説明することにあります．グラフの構築自体は劣モジュラ関数を知らなくても頭をひねればできるのですが，劣モジュラ関数との関係を意識することで以下のようなメリットがあると考えています．

与えられた問題が最小カットで解けるのか解けないのかの判別がしやすい．
劣モジュラ関数最小化の形にしてしまえば，機械的にグラフを構築することができる．

個人的に 2 がけっこー嬉しいです．というのも，燃やす埋める問題におけるグラフ構築方法は文献によって方法が様々あり，さらに頭を使って工夫しないといけないものが多いという感覚が個人的にはありました．慣れた人はうまくやれば良いと思うのですが，慣れていない人は結構混乱するような…．

劣モジュラ関数の最小化の形に落としてしまえば，あまり頭を使わずにグラフを構築する方法論が既に確立されているためこれに乗っかることができる，というのがメリットかもしれないな〜と思っています．

グラフ構築の手順

1. 最小化問題にする

まず，問題が最大化問題になっている場合，コストの符号を反転させるなどして最小化問題にします．関数値が負になっても特に問題はないので，気にせず符号を反転させてOKです．最終的に出てくる最適値の符号も反転して出てくることには注意．

2. 1-3変数の劣モジュラ関数の和の形で書く

うまく変数および関数を設定して，与えられた問題を

$\begin{align*} \kappa + \sum_i \theta_i (x_i) + \sum_{i< j} \phi_{ij} (x_i, x_j) + \sum_{i< j< k} \psi_{ijk} (x_i, x_j, x_k) \end{align*} \tag{1}$

の最小化問題として定式化します．ただし， $x_1, \ldots, x_n$ は $\{0, 1\}$ の値をとる変数であり， $\theta_i (x_i)$ , $\phi_{ij}(x_i, x_j)$ , $\psi_{ijk}(x_i, x_j, x_k)$ はそれぞれ1変数，2変数，3変数の劣モジュラ関数とします．また， $\kappa$ は定数項です．定義より，1変数関数は自動的に劣モジュラ関数になることに注意して下さい．

$x_1, \ldots, x_n$ は「アイテム $i$ を取るなら1, 取らないなら0」のような変数にするとうまくいくことが多いです．単純な問題なら2変数まであれば十分なことも多いと思います．(「アイテム $i$ を取ったときにアイテム $j$ を取るとコスト10かかる」などは2変数関数で表せます)

うまく劣モジュラ関数になってくれない場合，ビットを反転させればうまく行く場合があります． $x_i$ を「アイテム $i$ を取るなら0，取らないなら1」という変数に取り直すイメージです．この辺りは試行錯誤が必要な場所になります（機械的とは何だったのか）．

3. グラフを構築する

さて (1) の最小化問題として定式化できたら，いよいよグラフを構築します．

まず，頂点集合 $\{s, t, v_1, \ldots, v_n \}$ を用意します． $s, t$ は $s$ - $t$ カットを考えるための頂点であり，頂点 $v_i$ は変数 $x_i$ に対応します．この頂点集合に，容量付きの辺及び補助頂点を追加していきます．

辺の引き方，というかコストのかかり方の基本的な考え方は，

容量 $C$ の辺 $i \rightarrow j$ は，頂点 $i$ に値 0 が，頂点 $j$ に値 1 が割り当てられた場合にのみコスト $C$ を発生させる
$s$ - $t$ カットなので $s$ には必ず 0 が， $t$ には必ず 1 が割り当てられる
辺の容量は非負でなければならない

の3つです．

重要なこととして，(1) の各項は独立に考えて良いです．つまり，ある項 $T$ のことを考える時は，それ以外の項は完全に無視して $T$ をうまく表現することだけを考えればいいです．些細なことですが，このことに注意すると思考リソースがかなり節約できる気がします．

ただし，このとき頂点間に多重辺を引いてしまう可能性があります．多重辺があっても動くような最小カットアルゴリズムの実装なら問題ありませんが，不安な場合や計算時間がギリギリの場合は最小カット問題を解く前に多重辺を解消した方がいいかもしれません．

3-0. 定数項

まず定数項 $\kappa$ ですが，これは最適化と関係ないので無視してOKです．あとで目的関数値が正しくなるよう調整するために， $R$ という変数に加算して記憶することにします: $R \leftarrow 0$ と初期化しておいて， $R \leftarrow R + \kappa$ ．

3-1. 1変数関数

ここから辺を引いていきます．

辺の容量が非負でなければならないという要請から，場合分けが必要です．

$\theta_i(0) \leq \theta_i(1)$ のとき

$s$ から $v_i$ に容量 $\theta_i(1) - \theta_i(0)$ の辺を引く．
$R \leftarrow R + \theta_i(0)$ とする．

上記のような辺の引き方をすることで， $x_i = 0$ のときコスト0が， $x_i = 1$ のときコスト $\theta_i(1) - \theta_i(0)$ がかかるようにできます．これに定数 $\theta_i(0)$ を足してやればもとの $\theta_i(x_i)$ を表せます．

$\theta_i(0) > \theta_i(1)$ のとき

$v_i$ から $t$ に容量 $\theta_i(0) - \theta_i(1)$ の辺を引く．
$R \leftarrow R + \theta_i(1)$ とする．

1つ目の場合と同様にすると辺の容量が負になってしまうため，少し処理を変える必要があります．考え方は同じ．

f:id:Theory_and_Me:20200316174011p:plain:w540

3-2. 2変数関数

簡単のため，関数値を以下のような表の形式で書くことにします．

f:id:Theory_and_Me:20200316171022p:plain:w400

まず，次の図のように関数を分解します． f:id:Theory_and_Me:20200316165843p:plain このとき，第1項は定数関数，第2項は $i$ のみに依存する1変数関数，第3項は $j$ のみに依存する1変数関数になっているので，3-0, 3-1 で説明した方法で処理できます．

第4項について考えます．これは， $v_i$ から $v_j$ に容量 $B+C - A-D$ の辺を引くことで表現できます．確かに $x_i = 0$ , $x_j = 1$ の時のみコスト $B+C - A-D$ がかかり，それ以外の時はコストは0になることがわかると思います．

f:id:Theory_and_Me:20200316174516p:plain:w250

ここで， $B+C - A-D$ が非負であることが要請されますが，劣モジュラ性によりこれは必ず成り立ちます．劣モジュラ性はここに効いているんですね．

3-3. 3変数関数

場合分けが必要です．簡単のため，次の図のように $A$ - $H$ の記号を定めます． f:id:Theory_and_Me:20200316171912p:plain:w400

$P := (A+D+F+G)-(B+C+E+H)$ とおき， $P$ の符号で場合分けします．

(a) $P \geq 0$ のとき

$P_1 = F-B$ , $P_2 = G-E$ , $P_3 = D-C$ , $P_{23}= (B+C)-(A+D)$ , $P_{31} = (B+E)-(A+F)$ , $P_{12} = (C+E)-(A+G)$ とおき，関数を以下のように分解します． f:id:Theory_and_Me:20200316170220p:plain

このとき，右辺第1項は定数，第2-4項は1変数関数，第5-7項は2変数関数になっていることがわかるので，3-0, 3-1, 3-2 で説明した方法で処理します．もとの3変数関数の劣モジュラ性より $P_{23} \geq 0, P_{31} \geq 0, P_{12} \geq 0$ が成り立つことに注意すると，第5-7項の2変数関数は劣モジュラ関数になっていて，ちゃんとグラフ表現できることが保証されます．

第8項について考えます．これは，

補助頂点 $u_{ijk}$ を追加する．
$v_i$ から $u_{ijk}$ に容量 $P$ の辺を引く
$v_j$ から $u_{ijk}$ に容量 $P$ の辺を引く
$v_k$ から $u_{ijk}$ に容量 $P$ の辺を引く
$u_{ijk}$ から $t$ に容量 $P$ の辺を引く
$R \leftarrow R - P$

とすることで表現できます．

f:id:Theory_and_Me:20200316211129p:plain:w250

なぜこれで表現できるかを説明します．

グラフ表現可能性の定義より，補助頂点に対する値の割り当ての中でカット値が最小になるものが表現されると考えれば良いです．例えば， $x_i=0, x_j=0, x_k=0$ の場合， $u_{ijk}$ に0が割り当てられた場合はカット値は $P$ ，1が割り当てられた場合はカット容量は $3 \cdot P$ となりますが，このうち $P$ が表現されます．

f:id:Theory_and_Me:20200316215056p:plain:w500

このことから， $x_i, x_j, x_k$ に対するそれぞれの割り当てで表現される値は次の図のようになります．

f:id:Theory_and_Me:20200317174526p:plain:w500

このように， $x_i=1, x_j=1, x_k=1$ の場合にのみ関数値 0 が表現され，それ以外の場合は関数値 $P$ が表現されることになります．あとは全体に定数 $-P$ を足してやれば (これが $R \leftarrow R-P$ に対応する)，所望の関数が表現されるというわけです．

(b) $P \lt 0$ のとき

$P \geq 0$ の場合と考え方はほとんど一緒です．

$P_1 = C-G$ , $P_2 = B-D$ , $P_3 = E-F$ , $P_{32}= (F+G)-(E+H)$ , $P_{13} = (D+G)-(C+H)$ , $P_{21} = (D+F)-(B+H)$ とおき，関数を以下のように分解します． f:id:Theory_and_Me:20200316170250p:plain

第8項について考えます．これは，

補助頂点 $u_{ijk}$ を追加する．
$s$ から $u_{ijk}$ に容量 $-P$ の辺を引く
$u_{ijk}$ から $v_i$ に容量 $-P$ の辺を引く
$u_{ijk}$ から $v_j$ に容量 $-P$ の辺を引く
$u_{ijk}$ から $v_k$ に容量 $-P$ の辺を引く
$R \leftarrow R + P$

とすることで表現できます．これで表現できる理由は (a) と同様なので，考えてみてください．

f:id:Theory_and_Me:20200316211331p:plain:w250

3-4. 4変数以上でグラフ表現できる関数

4変数以上の関数にはグラフ表現できないものが存在するのですが，全ての4変数以上の関数がグラフ表現できないわけではありません．

特に，以下の2つは容易にグラフ表現できる上に汎用性が高いので，覚えておいて損はないかもしれません．

引数全てが 1 のとき $P\ (\lt0)$ ，それ以外のとき 0 をとる関数

すなわち以下のような $n$ 変数関数 $\zeta(x_1, \ldots, x_n)$ のことです:

$\begin{align*} \zeta(x_1, \ldots, x_n) = \begin{cases} P \quad (x_1 = x_2 = \ldots = x_n = 1)\\ 0 \quad (\mathrm{otherwise}). \end{cases} \end{align*}$

これは，

補助頂点 $u$ を追加する．
$v_i\ (i=1, \ldots, n)$ から $u$ に容量 $-P$ の辺を引く
$u$ から $t$ に容量 $-P$ の辺を引く
$R \leftarrow R + P$

で表現できます．理由は3変数関数を表現する際に使ったロジックと全く一緒なので，図を書いて考えてみてください．

引数全てが 0 のとき $P\ (\lt0)$ ，それ以外のとき 0 をとる関数

すなわち以下のような $n$ 変数関数 $\eta(x_1, \ldots, x_n)$ のことです:

$\begin{align*} \eta(x_1, \ldots, x_n) = \begin{cases} P \quad (x_1 = x_2 = \ldots = x_n = 0)\\ 0 \quad (\mathrm{otherwise}). \end{cases} \end{align*}$

これは，

補助頂点 $u$ を追加する．
$u$ から $v_i\ (i=1, \ldots, n)$ に容量 $-P$ の辺を引く
$s$ から $u$ に容量 $-P$ の辺を引く
$R \leftarrow R + P$

で表現できます．これも図を書いてみれば理由はすぐにわかると思います．

4. 最小 $s$ - $t$ カット問題を解いて答えを得る

最後に，構築されたグラフにおいて $s$ - $t$ カットを求めます．使うアルゴリズムは Ford-Fulkerson でも Edmonds-Karp でも Dinic でも Goldberg-Tarjan でも何でもどうぞ．

最小カット容量値が得られたら，ここまで計算しておいた $R$ を足してやることで元の問題の最小値が求まります．元の問題が最大化問題なら符号を反転することをお忘れなく．

最適値だけでなく最適解も必要な場合は，最小カットにおいて頂点 $v_i$ に0が割り当てられているか1が割り当てられているかを見ることで $x_i$ の値を決めることができます．

例題

MUL (ARC 85)

atcoder.jp

詳しい設定はリンク先を読んで頂くとして，とりあえず最大化問題になっているので符号を入れ替えて最小化問題にしてやって整理すると，

各宝石 $i$ を割るか割らないか選ぶ
宝石 $i$ を割らなければ $-a_i$ 円貰う
ただし， $j$ が $i$ で割り切れるとき，「宝石 $i$ を割るけど宝石 $j$ を割らない」は許されない
貰う合計金額を最小化せよ

ということになります．これは， $x_i$ を「宝石 $i$ を割るとき1, 割らないとき0」という変数と考えて，

$\theta_i (0) = -a_i, \theta_i (1) = 0$
$\phi_{ij} (0, 0) = \phi_{ij} (0, 1) = \phi_{ij} (1, 1) = 0, \phi_{ij} (1, 0) = +\infty$

なる関数を用意して，

$\begin{align*} \sum_i \theta_i (x_i) + \sum_{i| j} \phi_{ij} (x_i, x_j) \end{align*}$

を最小化する問題として捉えられます．（ここまで前の記事と同じ）

さて，上の手順に従えばこの場合のグラフ構築の手順は簡単で，

$i=1, \ldots, N$ に対して， $-a_i \gt 0$ ならば $v_i \rightarrow t$ に容量 $-a_i$ の辺を引く． $-a_i \lt 0$ ならば $s \rightarrow v_i$ に容量 $a_i$ の辺を引き， $R \leftarrow R-a_i$ とする．
$i=1, \ldots, N, j=i+1, \ldots, N$ に対して， $j$ が $i$ で割り切れるならば， $j \rightarrow i$ に容量 $\infty$ の辺を引く．

とすれば OK です．

Petya and Graph (Educational Codeforces Round 55)

codeforces.com

この問題も最大化問題なので符号を反転して最小化問題にして少し考えると

グラフ $G=(V, E)$ がある
各頂点を選ぶか選ばないか決める
頂点 $i$ を選ぶと重み $a_i\ (a_i>0)$ を得る
頂点 $i$ と頂点 $j$ を同時に選び， $ij$ 間に辺がある場合，重み $-w_{ij}\ (w_{ij}>0)$ を得る
重みの和を最小化せよ．

という問題になります．これは， $x_i$ を「頂点 $i$ を選ぶとき1, 選ばないとき0」という変数と考えて，

$\theta_i (0) = 0, \theta_i (1) = a_i$
$\phi_{ij} (0, 0) = \phi_{ij} (0, 1) = \phi_{ij} (1, 0) = 0, \phi_{ij} (1, 1) = -w_{ij}$

なる関数を用意して

$\begin{align*} \sum_{i \in V} \theta_i (x_i) + \sum_{(i, j) \in E} \phi_{ij} (x_i, x_j) \end{align*}$

を最小化する問題として捉えられます．（ここまで前記事と同じ）

さて，上の手順に従うと，以下のようにグラフを構築すれば OK です．

$i=1, \ldots, n$ に対して， $s \rightarrow v_i$ に容量 $a_i$ の辺を引く．
入力のグラフの各辺 $(i, j)$ について， $v_j \rightarrow t$ に容量 $w_{ij}$ の辺を引き， $R \leftarrow R - w_{ij}$ とし， $v_i \rightarrow v_j$ に容量 $w_{ij}$ の辺を引く．

上の手順は $\phi_{ij}$ を分解してそれぞれ表現していますが， $\phi_{ij}$ が 3-4 で説明した「全ての引数が1のときに $P\ (P \lt 0)$ ，それ以外のとき 0 をとる関数」になっていることに注意すると次のような表現も可能です．

$i=1, \ldots, n$ に対して， $s \rightarrow v_i$ に容量 $a_i$ の辺を引く．
入力のグラフの各辺 $(i, j)$ について，補助頂点 $u_{ij}$ を用意し， $v_i \rightarrow u$ , $v_j \rightarrow u_{ij}$ , $u_{ij} \rightarrow t$ にそれぞれ容量 $w_{ij}$ の辺を引き， $R \leftarrow R - w_{ij}$ とする．

ここから分かるように，グラフ表現の方法は一意ではありません．

まとめ

グラフ表現可能な劣モジュラ関数の最小化問題の形にしてしまえば，かなり機械的にグラフを構築できることが分かっていただけたと思います．

色々と場合わけでややこしくなってしまいましたが，要はやっていることは「定数は記憶しておいて後は辻褄を合わせる」「 $s \rightarrow v_i$ もしくは $v_i \rightarrow t$ で`1変数関数を表現する」「 $v_i \rightarrow v_j$ で2変数関数を表現する」「補助頂点をうまく使って3変数以上の関数を表現する（できない場合もある）」の4つで，関数をうまく分解することでこの4つを使える形に持っていっている，というのが直感的な理解だと思います．

もちろん，ここで書いた手順は一つの例に過ぎないので，自分にあった方法でグラフを構築すればいいと思います．皆様，良き燃やす埋めるライフを！

もしかしたら，もう少し発展的な内容を扱ったその③を書くかもしれません．ただ，書くにしても色々調べる必要があるので時間はかかりそうです．

参考文献

[1] V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts? IEEE Transaction on Pattern Analysis and Machine Intelligence, 26(2):147–159, 2004.

基本的にこの記事の内容は [1] の内容をまとめたものになっているので，詳しく知りたい方はこちらを読んで頂くと理解が深まると思います．一部の図を [1] からお借りしています．

私と理論

数学の話を主に書きます

燃やす埋める問題と劣モジュラ関数のグラフ表現可能性その② グラフ構築編

グラフ構築の手順

1. 最小化問題にする

2. 1-3変数の劣モジュラ関数の和の形で書く

3. グラフを構築する

3-0. 定数項

3-1. 1変数関数

$\theta_i(0) \leq \theta_i(1)$ のとき

$\theta_i(0) > \theta_i(1)$ のとき

3-2. 2変数関数

3-3. 3変数関数

(a) $P \geq 0$ のとき

(b) $P \lt 0$ のとき

3-4. 4変数以上でグラフ表現できる関数

引数全てが 1 のとき $P\ (\lt0)$ ，それ以外のとき 0 をとる関数

引数全てが 0 のとき $P\ (\lt0)$ ，それ以外のとき 0 をとる関数

4. 最小 $s$ - $t$ カット問題を解いて答えを得る

例題

MUL (ARC 85)

Petya and Graph (Educational Codeforces Round 55)

まとめ

参考文献

グラフ構築の手順

1. 最小化問題にする

2. 1-3変数の劣モジュラ関数の和の形で書く

3. グラフを構築する

3-0. 定数項

3-1. 1変数関数

のとき

のとき

3-2. 2変数関数

3-3. 3変数関数

(a) のとき

(b) のとき

3-4. 4変数以上でグラフ表現できる関数

引数全てが 1 のとき ，それ以外のとき 0 をとる関数

引数全てが 0 のとき ，それ以外のとき 0 をとる関数

4. 最小 - カット問題を解いて答えを得る

例題

MUL (ARC 85)

Petya and Graph (Educational Codeforces Round 55)

まとめ

参考文献

$\theta_i(0) \leq \theta_i(1)$ のとき

$\theta_i(0) > \theta_i(1)$ のとき

(a) $P \geq 0$ のとき

(b) $P \lt 0$ のとき

引数全てが 1 のとき $P\ (\lt0)$ ，それ以外のとき 0 をとる関数

引数全てが 0 のとき $P\ (\lt0)$ ，それ以外のとき 0 をとる関数

4. 最小 $s$ - $t$ カット問題を解いて答えを得る