競プロ界隈でいわゆる「燃やす埋める問題」と呼ばれる問題群があります．（このネーミングが適切かどうかには賛否両論あるようですが，広く用いられているようなので本記事中では用います）それほど出題頻度は高くないようですが，知らないと解くのが難しいタイプの問題なので，前もって勉強しておくことが重要です．

この燃やす埋める問題ですが，競プロの界隈から離れて離散最適化研究の界隈から見ると，実は「劣モジュラ関数のグラフ表現可能性」と呼ばれるトピックと非常に強く関係しています．この「燃やす埋める問題」と「劣モジュラ関数のグラフ表現可能性」との関係を知っていると，

与えられた問題が最小カットを用いて解けるのかどうか判断しやすくなる
最小カットを用いて解ける場合に，グラフの構築が機械的にできるようになる

というメリットがあるような気がします．

燃やす埋める問題を解説している記事はたくさんありますが，劣モジュラ関数の観点から論じているものは殆どないようだったのでこの記事で概観してみました．

燃やす埋める問題と $\{0, 1\}^n$ 上の関数の最小化問題

いわゆる「燃やす埋める問題」とは以下のような問題です．

$n$ 個のアイテムがあるとき，それぞれを「燃やす」か「埋める」か決める．このとき，「燃やす」「埋める」のパターンに応じてお金がかかったり逆にお金が貰えたりする（例えば，「アイテム1を燃やした10円かかる」「アイテム2を燃やしたときにアイテム3を埋めたら20円もらえる」など）．このとき，うまく各アイテムを「燃やす」か「埋める」か決めて，必要なお金を最小化せよ．

「アイテム2を燃やしたときにアイテム3は埋められない」などの「禁止」の制約もあり得ますが，これはお金 $+\infty$ がかかると考えればOKです．また，最大化問題の場合は符号を反転させればOKです．

さて，このような問題は $\{0, 1\}^n$ 上の関数 $f: \{0, 1\}^n \to \mathbb{R}\cup\{+\infty\}$ を最小化する問題と考えることができます．各アイテムが変数 $x_i$ に対応していて， $x_i=0$ が「アイテム $i$ を燃やす」ことに， $x_i=1$ が「アイテム $i$ を埋める」ことに対応します．そして，全体でかかるお金が $f(x_1, x_2, \ldots, x_n)$ で表されていて， $x_1, x_2, \ldots, x_n$ をうまく決めることで $f$ を最小化します．

この最小化問題は， $f$ に何の制限もなければNP-Hardです．これが効率的に解けるはずがないっていうのは直感的にも分かりますよね．

劣モジュラ関数

さて，気になるのは関数のクラスを制限すれば効率的に解くことができるかどうか，ということです．このトピックに関しては様々な研究がなされていますが，特に重要なのがこの記事の主題である劣モジュラ関数です．

劣モジュラ関数とは， $\{0, 1\}^n$ 上の関数 $f$ で，任意の $x, y \in \{0, 1\}^n$ に関して

$\begin{align*} f(x)+f(y) \geq f(x \land y) + f(x \lor y) \end{align*} \tag{1}$

が成り立つもののことを言います．ただし， $x \land y$ は $x$ と $y$ に関して変数ごとに論理積をとったものを， $x \lor y$ は $x$ と $y$ に関して変数ごとに論理和をとったものを表すこととします．

文献によっては，劣モジュラ関数の定義は集合 $V$ 上の集合関数 $f: 2^V \rightarrow \mathbb{R}$ で，任意の $S, T \subseteq 2^V$ に関して

$\begin{align*} f(S)+f(T) \geq f(S \cap T) + f(S \cup T) \end{align*} \tag{2}$

が成り立つようなもの，となっていることがあります（というかこっちの方が多い？）． (2)における集合を指示関数に読み替えることで，(1)と(2)は等価であることが容易に確かめられます．今回は(1)の定義で話を進めていきます．

実は劣モジュラ関数の最小化問題は多項式時間で解くことが可能です．(1)という緩い（?）条件を加えるだけで $\{0, 1\}^n$ 上の関数の最小化が多項式時間でできるというのはけっこー驚きです．また，ここでは詳しく述べませんが，劣モジュラ関数は見方を変えると直感的で自然な解釈が可能で（限界効用逓減性），様々な現実の問題をモデリングすることができます．このように，最適化のしやすさとモデリングにおける有用性を兼ね備えていることから，劣モジュラ関数は様々な分野で重要視されています．

ちなみに，劣モジュラ関数の最大化はNP-Hardですが，効率的な近似アルゴリズムが設計できることが知られており，こちらに関しても様々な結果が知られています．本記事では最大化の話はしませんがこれはこれで面白いトピックです．

グラフ表現可能な劣モジュラ関数

さて，劣モジュラ関数は多項式時間で最小化できると言いましたが，「簡単にできる」とは言っていません．というのも，多項式時間とはいえども $n$ の肩に乗る指数が大きく，アルゴリズムも非常に複雑で実装が難しいからです．これでは現実の問題を解くために用いることは難しそうです…

しかし光明はあります．実は一部の劣モジュラ関数は，「適切なグラフを作りその上で最小カット問題を解くことで最小化することができる」ことが知られています．最小カット問題は比較的シンプルなアルゴリズム (Dinic のアルゴリズムなど) で高速に解くことができるので，めでたしめでたしという訳です．

上記の内容を正確に議論するため，グラフ表現可能な関数という概念を導入します． $\{0, 1\}^n$ 上の関数 $f$ がグラフ表現可能であるとは，ある非負枝容量付き有向グラフ $G=(V, E)$ と定数 $\kappa$ が存在して，

$V \supseteq \{ s, t, 1, \ldots, n \}$
任意の $x=(x_1, \ldots, x_n) \in \{ 0, 1\}^n$ に対して $f(x) = \mathrm{min} \{ C(X) \mid X\ は\ s {\rm -} t\ カット, X(i) = x_i\ (i=1, \ldots, n) \} + \kappa$

が成り立つことを言います [1]．ただし，ここでいう $s$ - $t$ カットとは，グラフの頂点 $v \in V$ に対する 0-1 割り当て $X: V \to \{0, 1\}$ のうち， $X(s)=0, X(t)=1$ を満たすもののことを言います．また， $C(X)$ はカット $X$ のカット容量を表します．

この定義はすぐには分かりづらいのですが，要は

$\{s, t, 1, \ldots, n\}$ にいくつかの補助頂点を加えたものを頂点集合 $V$ として，そこに適当に容量つきの辺を引いてグラフ $G = (V, E)$ を作る
$x=(x_1, \ldots, x_n) \in \{ 0, 1\}^n$ が与えられたとき，頂点 $i\ (i=1, \ldots, n)$ の割り当てを $x_i$ に固定した $s$ - $t$ カット集合を考える（追加した補助頂点の割り当ては任意なので，複数の $s$ - $t$ カットが考えられる）．この $s$ - $t$ カット集合の中でカット容量が最小になるものを $X^{*}$ としたとき， $C(X^{*}) + \kappa = f(x)$ となる．これが全ての $x \in \{ 0, 1\}^n$ について成り立つ．

ということです．

少し考えれば，このような性質を満たすグラフ上で最小 $s$ - $t$ カットを求めれば， $f$ の最小化ができることが分かると思います．また，最小カットにおける頂点 $1, \ldots, n$ の割り当てを見ることで，もとの問題の最適解も復元できます．

実は，任意のグラフ表現可能な関数は劣モジュラ関数です．このことはカット関数そのものが必ず劣モジュラ関数になることと，少々の式変形から導くことができます．すなわち，「 $\{0, 1\}^n$ 上の関数」と「劣モジュラ関数」と「グラフ表現可能な関数」は次の図のような関係になっています．

f:id:Theory_and_Me:20200313154438p:plain — 関数クラスの関係

ここまで導入した言葉を用いると，競プロにおける「燃やす埋める問題」は，「グラフ表現可能な劣モジュラ関数を最小カットアルゴリズムによって最小化する問題」に概ね一致します．（ビット反転を考慮する必要があるため「概ね」と言っています．詳しくは後で説明します．）

どのような関数がグラフ表現可能なのか？

さて，ここまでくると

どのような関数がグラフ表現可能なのか？
どのようなグラフを構築すれば表現できるのか？

が気になってきます．これらに関する知見があれば，問題が与えられたときにそれがグラフカットによって解くことが可能かどうかが判別でき，さらに適切なグラフを構築することで最小化を行うことができるからです．

これらの問いへの解答は離散最適化において重要なトピックであり，様々な研究がなされてきました．とりあえずこの記事の中では1つ目の問いについての代表的な結果を示します．問題を解く上では2つ目の問いも重要なのですが，長くなってしまうのでについては次の記事（その②）に書こうと思います．

1変数関数＋2変数劣モジュラ関数

さて，まずシンプルな例として以下の形で表される関数について考えてみます．

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

ただし， $\phi_{ij}(x_i, x_j)$ は2変数劣モジュラ関数とします（すなわち， $\phi_{ij}(0, 1)+ \phi_{ij}(1, 0) \geq \phi_{ij}(0, 0) + \phi_{ij}(1, 1)$ が成立）．簡単な計算より，1変数関数と劣モジュラ関数，及び劣モジュラ関数と劣モジュラ関数の和はまた劣モジュラ関数になるので，上記の形で表される関数は劣モジュラ関数になります．

この劣モジュラ関数はグラフ表現可能でしょうか？答えはYESです．1変数関数と2変数劣モジュラ関数の和の形で表される任意の関数は，グラフ表現可能であることが知られています [2]．

具体的なグラフの構築方法はその②で説明しますが，頂点集合 $V=\{s, t, 1, \ldots, n\}$ を用意して，

1変数関数1つにつき辺を高々1本
2変数関数1つにつき辺を高々3本

加えればグラフを構築できます．そのため，構築されるグラフの頂点数，辺数も $n$ の多項式で抑えられ，最小カットにより効率的に最小化できます．

例題

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*}$

を最小化する問題として捉えられます．

さて，簡単な計算により $\phi_{ij}$ は劣モジュラ関数であることがわかるので，この関数はグラフ表現可能であり，最小カットを用いて最小化できることが分かります．

Petya and Graph (Educational Codeforces Round 55)

codeforces.com

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

グラフ $G=(V, E)$ がある
各頂点を選ぶか選ばないか決める
頂点 $i$ を選ぶと重み $a_i$ を得る
頂点 $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*}$

を最小化する問題として捉えられます．

$w_{ij}>0$ より $\phi_{ij}$ は劣モジュラ関数であることがわかるので，この関数はグラフ表現可能であり，最小カットを用いて最小化できることが分かります．

1変数関数＋2変数劣モジュラ関数+3変数劣モジュラ関数

さて，それではもう少し広い関数のクラスとして，以下の形で表される関数はどうでしょうか？

$\begin{align*} \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{4}$

ただし， $\psi_{ijk}(x_i, x_j, x_k)$ は3変数劣モジュラ関数とします．

この劣モジュラ関数はグラフ表現可能でしょうか？なんとこの答えもYESです．1変数関数と2変数劣モジュラ関数と3変数劣モジュラ関数の和の形で表される任意の関数も，グラフ表現可能であることが知られています [3]．

具体的なグラフの構築方法はその②で説明しますが，頂点集合 $V=\{s, t, 1, \ldots, n\}$ を用意して，

1変数関数1つにつき辺を高々1本
2変数関数1つにつき辺を高々3本
3変数関数1つにつき補助頂点を高々1つ，辺を高々16本

加えればグラフを構築できます．そのため，構築されるグラフの頂点数，辺数も $n$ の多項式で抑えられ，最小カットにより効率的に最小化できます．辺だけではなく補助頂点を加える必要があるのが2変数関数と違うところですね．

4変数以上の劣モジュラ関数

さて，ここまできたら次に気になるのは4変数劣モジュラ関数が入ってきてもグラフ表現できるのか！？になりますが，良いニュースはここでおしまいです．

実は，4変数以上の劣モジュラ関数の中には，いくら頂点や辺を付け加えたとしても絶対にグラフ表現できないものが存在することが，2009年に Živný らによって示されています [4]．まだ僕はこの証明はあまり理解できていません．悲しいね．詳しい人曰く，「グラフ表現可能ならこういう不等式を満たさないといけないけど，この4変数関数は満たしてないから，グラフ表現不可能」という論法で，そこまで難しくは無いとのことです．

ビット反転

さて，こんな感じで関数がグラフ表現できる条件を挙げてきましたが，ちょっと厄介な存在が残っています．それは，「劣モジュラ関数ではないけれど，適切にビット反転すると劣モジュラ関数になるような関数の存在」です．

例えば， $\phi_{ij}(0, 0) = 1, \phi_{ij}(1, 0) = 0, \phi_{ij}(0, 1) = 0, \phi_{ij}(1, 1) = 2$ なる2変数関数 $\phi_{ij}(x_1, x_2)$ は劣モジュラ関数ではありません．しかし，ここで新しく $\phi'_{ij}(x_1, x_2) = \phi_{ij}( \lnot x_1, x_2)$ という， $x_2$ を反転させた関数 $\phi'_{ij}(x_1, x_2)$ を考えてみます．すると， $\phi’_{ij}(0, 0) = 0, \phi’_{ij}(1, 0) = 1, \phi’_{ij}(0, 1) = 2, \phi’_{ij}(1, 1) = 0$ となるため， $\phi'_{ij}(x_1, x_2)$ は劣モジュラ関数になります．

そして，「適切なビット反転をすることでグラフ表現可能な劣モジュラ関数になるような関数」もまた，最小カットで最小化可能です．この場合，含まれる全ての項に関して同時にビット反転をする必要があることに注意してください．例えば $\phi_{12}(x_1, x_2) + \phi_{23}(x_2, x_3)$ のような形の関数において $x_2$ を反転させる場合， $\phi_{12}(x_1, \lnot x_2)$ でだけなく $\phi_{23}( \lnot x_2, x_3)$ も劣モジュラ関数になる必要がある，といった感じです．

「適当なビット反転によってグラフ表現可能な劣モジュラ関数にできるかどうか」を効率的に判定するのは難しそうです．そもそも与えられた劣モジュラ関数がグラフ表現可能かを判定する効率的な方法がわかっていないとのこと．そのため，競プロの問題として出てきたら試行錯誤して良い反転を見つける必要がありそうです．依存関係が二部グラフになっていたりすると，ビット反転しやすかったりするようです．

まとめ

競プロでいう「燃やす埋める問題」は「グラフ表現可能な劣モジュラ関数を最小カットによって最小化する問題」だよ
1-3変数劣モジュラ関数の和の形で表される劣モジュラ関数はグラフ表現可能だよ
4変数が入ってくると無理な場合があるよ
ビット反転も考慮する必要があるよ

具体的なグラフの構築方法についてはその②で説明する予定です．

グラフ表現可能性について色々教えてくれた，ゆにさん(@yuni_jp)に感謝！

参考文献

[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.
[2] P. L. Ivănescu. Some network flow problems solved with pseudo-boolean programming. Operations Research, 13(3):388–399, 1965
[3] A. Billionnet and M. Minoux. Maximizing a supermodular pseudoboolean function: a polynomial algorithm for supermodular cubic functions. Discrete Applied Mathematics, 12:1–11, 1985
[4] S. Živný, D. A. Cohen and P. G. Jeavons. The Expressive Power of Binary Submodular Functions. Discrete Applied Mathematics, 157(15):3347–3358, 2009

ちなみに [1] の論文は画像系のトップジャーナルの論文です．なぜこの話題が画像系のジャーナルに載っているかというと「マルコフ確率場 (MRF) のMAP推定問題」という，画像の復元•ノイズ除去をする際に現れる問題が，実はいわゆる燃やす埋める問題になることが知られているからです．競プロは現実問題の役に立つ！（？）

私と理論

数学の話を主に書きます

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

燃やす埋める問題と $\{0, 1\}^n$ 上の関数の最小化問題

劣モジュラ関数

グラフ表現可能な劣モジュラ関数

どのような関数がグラフ表現可能なのか？

1変数関数＋2変数劣モジュラ関数

例題

MUL (ARC 85)

Petya and Graph (Educational Codeforces Round 55)

1変数関数＋2変数劣モジュラ関数+3変数劣モジュラ関数

4変数以上の劣モジュラ関数

ビット反転

まとめ

参考文献

燃やす埋める問題と 上の関数の最小化問題

劣モジュラ関数

グラフ表現可能な劣モジュラ関数

どのような関数がグラフ表現可能なのか？

1変数関数＋2変数劣モジュラ関数

例題

MUL (ARC 85)

Petya and Graph (Educational Codeforces Round 55)

1変数関数＋2変数劣モジュラ関数+3変数劣モジュラ関数

4変数以上の劣モジュラ関数

ビット反転

まとめ

参考文献

燃やす埋める問題と $\{0, 1\}^n$ 上の関数の最小化問題