Proximity search：列挙アルゴリズムの新たな構築手法

本記事は「データ構造とアルゴリズム Advent Calendar 2019」３日目の記事です．
2 日目は @yurahunaさんによる「三角形分割の数え上げとランダムサンプリング」です．
4 日目は @ygussanyさんによる「群ラベル制約付き最短路問題」です．

この記事の元ネタは，STOC 2019で発表されたProximity searchに関する論文です．証明等に関しては省略します．詳しく知りたい方は下記文献にあたってください．また，グラフアルゴリズムにおける用語がわかる人を想定して記事を執筆しています．例えば，オーダー記法がなんとなくわかる，グラフは頂点と辺の組であることを知っている，二部グラフの定義を知っている，などです．

Alessio Conte and Takeaki Uno, "New polynomial delay bounds for maximal subgraph enumeration by proximity search", In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), pp. 1179-1190, 2019. DOI: https://doi.org/10.1145/3313276.3316402

部分グラフ列挙問題とフレームワーク

本記事では，次のような問題を解くための新たなフレームワークについて紹介します．

入力：ラベル付きグラフ$G$

出力：$G$に含まれていて，かつ，グラフクラス$\mathcal{C}$に属する$G$の部分集合全てを漏れなく重複なく出力せよ．ただし，同型なものであってもラベルが異なれば違う解とみなす．

上記の問題は一般に列挙問題と言われます．列挙問題は計算機科学の文脈で言えば割と古典的なものです．私が知る限り，遅くとも1950年代から研究が始まり，初期の頃は全域木の列挙などが注目されていました．これは回路の評価などに使われていたようです．全域木の他にも，$\mathcal{C}$としては，パスやサイクルが古典的な対象でした．

列挙問題における大きな問題の一つは，「網羅性」，つまり，数です．一般的に，解の個数は指数個あります．そのために起こった悲劇はお姉さん問題として知られています．したがって，少しでもマシにしようということで，包含に関して極大な解や極小な解に着目することが近年では多いですが，今度は問題自体が難しくなります．もうメチャクチャですが，研究者は頑張って研究しております．下は対象の例です．

極大クリークおよび極大独立点集合
極小支配集合
極小カット・セパレーター

また，膨大な数は列挙問題の難しさに拍車をかけます．それは「一意性」，つまり，「過去出力した解をもう一度出してはダメ」という制約です．愚直にやろうとするならば，今まで出力した解を保存しておき，新しい解を見つけた時にそれが出力済みかどうかを保存したものを利用してチェックするというものです．このように指数領域のメモリを使用するアプローチはともすると愚かなアルゴリズムになりがちですが，これらを効率よく管理し列挙するアプローチもあります．BDDやその派生であるZDDがその一つで，実際に強烈な速度で解を列挙します．

さて，この「網羅性」や「一意性」が列挙問題の難しさになるのですが，このような難しさを統一的な枠組みで解決する試みがあり，実際にいくつかのフレームワークが提案されています．ここでいうフレームワークは「ある性質を満たす何かを発見することができれば，アルゴリズムの正当性の細かな議論をすっ飛ばしてアルゴリズムを構成できる」というものです．列挙のフレームワークに関する入門的な内容に関しては下記文献を参照してください．

岡本吉央, 列挙の基本と基礎的なアルゴリズム, 電子情報通信学会誌, 95(6), 1057, pp.477-483, 2012.

ConteとUnoによるProximity searchは，特に極大な解を列挙するための新しいフレームワークを与えています．これにより，時間計算量の観点で効率良いアルゴリズムを構成することが可能になり，実際にいくつかの未解決問題を解いた，というのが彼らの論文の大きな貢献です．ただ，利点ばかりではなく，指数領域のメモリを消費してしまう，などのデメリットもあります．みなさん，この辺りを一般に解決すると難関国際会議に採択されますよ．

前準備

列挙アルゴリズムの評価方法について

上に述べたように，列挙問題は解の個数が入力サイズ$n$に対して指数，つまり，$\mathcal{O}(2^n)$となる場合が多いです．このような場合，入力サイズのみでアルゴリズムの性能を評価してしまうと，場合によっては悲観的な見積もりになります．
そこで，列挙の界隈では，入力サイズだけでなく出力数$M$に関しても考慮して計算量を見積もります．具体的には，$\mathcal{O}(M\cdot poly(n))$時間で動作するアルゴリズムをならし多項式時間と呼びます．このくらいになると，一般的には効率良いアルゴリズムだろうと言われます．図にすると次のような感じですね．直感的に説明すると「解一つあたり出力するのにかかる時間は，平均すると多項式で抑えられる」です．

図を入れたいなあ

ただ，次のようなシチュエーションを考えみましょう：ここは列挙居酒屋．飲み放題のコース．人数は10人．「全員にビールを！」しかし，この居酒屋が担保するのはならし多項式時間であるだけ...こんな悲劇が起こります．
最初の5人のビールは定数時間で来るが，後の5人の分は指数時間かかるだと！いつ乾杯するんだ...俺のビールはどこにある！まだ酒屋か！これが何回も続いてみましょう．喧嘩になります．人々が望むのは，最悪時でもせめてみんな同じ時間だけ待つ，つまり遅延の保証です．

列挙の人たちは，基本的に遅延の保証のあるアルゴリズムを構成しようすることを目標にします．ただ，人工的に遅延が多項式で抑えられない問題も作ることができます．この辺りは，遅延の意味で，どこからが難しい問題で，どこからが簡単かを発見できると嬉しいですね．
さて，Proximity searchにより効率良いアルゴリズムを構築することが可能になったと述べましたが，具体的にはこの遅延が多項式になるようなアルゴリズムを構築する手法を与えています．

Proximity search

列挙アルゴリズムは，一言で言うと，解グラフを明示的に，あるいは，暗黙的に構築し，その解グラフ上を探索することで解を列挙します．実際，様々な列挙アルゴリズムの構築フレームワークはこの枠組みに乗っています．みんな大好き逆探索法や，いにしえより存在するグレイコード，分割法もこの解釈でイケます．Proximity searchも，そんなフレームワークの一つです．

解が構成するグラフ

解グラフとは解を頂点とするグラフのことを言います．

図を入れたいなあ

列挙アルゴリズムが効率良いものになるかどうかは，このグラフをどう構築するか，つまり，どのような隣接関係を定義すれば良いか，がキーポイントになります．Proximity searchは，隣接関係$\mathtt{NEIGHBORS()}$を近接性$\tilde{\cap}$を導入することで定義して，効率良い列挙を実現しています．以上を踏まえて，彼らのメインの主張であるTheorem 13を見てみましょう（私が適当に訳しています）：

Theorem 13: 全てのproximity searchableな問題に対して，多項式遅延な列挙アルゴリズムを構成できる．

これは強烈ですね．じゃあ，proximity searchableな問題とはなんでしょうか．次の条件を満たしている問題がそれです（私が適当に訳しています）：

Definition 12: $\mathcal{P}$を列挙問題とし，その解集合$\mathcal{S}$は台集合$\mathcal{U}$の部分集合の集合からなる，つまり，$\mathcal{S} \subseteq 2^\mathcal{U}$とする．ここで，$\mathcal{P}$がproximity searchableであるとは，次を満たすような隣接関数$\mathtt{NEIGHBORS()}: \mathcal{S} \to 2^\mathcal{S}$と近接性$\tilde{\cap}: \mathcal{S} \times \mathcal{S} \to 2^\mathcal{U}$が存在する時をいう：

$\mathcal{P}$の解のうち，一つが多項式時間で求まる．

任意の二つの解$S, S^* \subseteq \mathcal{S}$に対して，$|S'\tilde{\cap} S^* | >| S \tilde{\cap} S^*|$となるような$S$に隣接する解$S' \in \mathtt{NEIGHBORS(S)}$が存在する．

$\mathtt{NEIGHBORS(S)}$が$|\mathcal{U}|$に関する多項式時間で計算可能である．

この中でも2と3がキモで，直感的には「今の解から見て，どんな解に対しても何らかの類似性のようなものが大きくなる現状よりマシな隣接解があり，さらに隣接するものはそんなに多くない」を満たすような隣接関数と近接性を定義できれば勝ち，言う感じですね．これが定義できれば，任意の解$S$から探索をスタートしても，隣接する解を再帰的に探していけば，任意の未発見の解$S^{*}$に必ずたどり着けます．しかも，1から，最初の解は多項式時間で見つかります．あ，解グラフが強連結であることは忘れずに証明してください．
ここまでくると普通のグラフ探索と何ら変わりません．しかも，隣にある解がそんなに多くないです．たとえ隣接する解全てが訪問済みであっても，その個数は多項式で抑えられているので，つまり，多項式遅延で列挙できるのです．さらに興味深いのは，$\tilde{\cap}$は証明の中にしか出てこず，アルゴリズムを計算する上では使用しません．このあたりがこのフレームワークの面白いところです．実際に論文に載っている擬似コードは恐ろしくシンプルです．ただ，擬似コード中でもわかるように，単純なグラフ探索同様，解を全て保存しています．これが領域が多項式で抑えられない理由です．

実際の例：極大誘導二部グラフ

細かい証明等は省略する代わりに，実例を見てみましょう．論文では，いくつかの問題に対して，実際に隣接関数と近接性を定義しています．最初に出てくる例は極大連結誘導グラフなので，これで説明しましょう．連結でない場合，二部性のあたりが面倒になるので，興味のある方は論文をあたってください．また，以下では連結の表記は省略します．

極大誘導二部グラフの隣接関数

まずは，隣接関数です（私が適当に訳しています）：

Definition 2: 極大誘導二部グラフ$B= (B_0, B_1)$と$v \notin B$に対して，$\mathtt{NEIGHBORS}(B_i, B_{1-i}, v) = \mathtt{COMP}({v}\cup (B_i \setminus N(v)) \cup B_{1-i})$とする．

ここで，$i$は0あるいは1が入ります．直感的な説明は，まず，$B_i$だけからなるグラフを考えます．そこに，$v$を無理やり突っ込みます．そうすると，$v$と隣接するいくつかの頂点が$B_i$にあるのでそれを全部削除します．その後で，$B_{1-i}$を加えます．こうすることで，誘導二部グラフが得られるのですが，残念ながら極大ではない可能性があるので，適当に頂点を加えていくことで極大化させます．これが$\mathtt{COMP}$に対応します．このようにして，隣接する解を全ての頂点$v \notin B$に対して計算して，先ほど載せた擬似コードに使います．具体的には，$\mathtt{NEIGHBORS}(B) = \bigcup_{v \notin B}\mathtt{NEIGHBORS}(B_i, B_{1-i}, v)$です．どうです？簡単でしょ？競プロ勢に見せたら30秒で実装しそうなアルゴリズムです．こんな簡単なアルゴリズムで本当に解けるの？と言う感じがしますが，ここは近接性をうまく導入しているので証明できる感じですね．

極大誘導二部グラフにおける近接性

多くの場合，近接性は頂点の順序で定義します．それに倣って，まずは誘導二部グラフにおける頂点の標準列を次のように定義します（私が適当に訳しています）．

Definition 4: $B$を誘導二部グラフとし，その頂点からなる標準列は$b_1, \dots, b_{|B|}$は，次のように定義される：$b_1$を$B$中の最小ラベルの頂点とする．$b_i$は$B\setminus{b_1, \dots, b_{i-1}}$中の頂点で，かつ，${b_1, \dots, b_i}$が連結となるような最小なラベルを持つ頂点である．

この標準列において重要なのは，どんなプレフィックスを持ってきても連結なものである，という点です．この点を使って，近接性を次のように定義します（私が適当に訳しています）．

Definition 5: 二つの解を$S, S^*$とし，$s^{*}_1, \dots, s^{*}_{|S^{*}|}$を$S^{*}$の標準列とする．この時，$S\tilde{\cap} S^*$は，$S$の要素で構成される$s^*_1, \dots, s^*_{|S^*|}$の最長プレフィックスとする．

まず自明にわかることは，$S = S^*$となった時，近接性は最大になります．また，この近接性の面白い性質は，今$S$に入っていない頂点$v \notin S$のうちどれか一つは，$\mathtt{NEIGHBORS}(S_i, S_{1-i}, v)$を計算することでプレフィックスが長くなるような解が得られる，という点です．つまり，ゴールである$S^*$を知らなくても，たかだか$n$回，$\mathtt{NEIGHBORS}$を辿れば$S^*$に到達できます．さらに，一つ頂点を追加するたびに確実に共通するプレフィックスが長くなる，つまり，$S^*$に近づくので，どのように$\mathtt{COMP}$を計算してもOKとなります．ここでお気付きの方もいるかもしれませんが，この定義は極大誘導二部グラフの列挙以外にも使えます．また，一般に交換則が成り立たないので気をつけてください．
さて最後に時間計算量です．ここで，$\mathcal{O}(n)$個の隣接解があり得て，極大化の計算$\mathtt{COMP}$も$\mathcal{O}(m)$時間で抑えられるので，最終的に得られる時間計算量は次のようになります（若干ステートメントを変更しています）：

Theorem 10: 極大連結誘導二部グラフは$\mathcal{O}(nm)$遅延で列挙できる．

今回紹介した論文では，他にもいくつかの問題を解いています．以下がそのリストとなっています．

さらに，ここでは詳細を省きますが，input-restricted problemと呼ばれる問題が多項式時間で解ける場合も，元の列挙問題がproximity searchableであることがわかっています．

まとめ

この論文の登場で列挙に関する潮目が変わりました．まずは問題がproximity searchableであるかどうかを調べることが必須となっています．もちろんこのフレームワークは最適性を保証しているわけではないので，今回の結果が直ちに分野を焼け野原にするものではありません．また，このフレームワークをうまく適用できなさそうだと思われている問題もいくつかあります．その一例としては，極大平面部分グラフの列挙問題です．さらには「解ける」問題ではなく「解けない」問題に対する直感も，与えることができていません．今後の列挙界隈はこのような問題を解明する方向で進んでいくと思われます．