$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\inset}[2]{\{#1 \mid #2\}}$ $\newcommand{\name}[1]{\emph{#1}}$ $\newcommand{\size}[2][]{\left| #2^{#1} \right|}$ $\newcommand{\sig}[1]{\mathcal{#1}}$

なんでお前解けるんだよ問題リスト：列挙版

chocobaby-aporo.hatenablog.com

みなさんに協力いただいてちょっと面白いリストができました． 一応私もアルゴリズムの勉強してお給料をいただいているので，自分の専門分野でのリストも作ってみようと思います． 独断と偏見で作っているので，お近くの先生にとって「これは違うだろ」とあれば優しく怒ってください．

とりあえず，列挙アルゴリズムについての概略です． アルゴリズムである問題が解けるよ〜っていう場合，具体的な答えを一つ見つけることが多いと思います． 「答えがあるけど見つけ方がわからん」みたいな問題もあるので，そちらが気になる人は TFNP（Total Function Nondeterministic Polynomial）とか調べるといいと思います． 日本人でもプロがいると思います． ともかく，効率良いアルゴリズムがあることを示す際には，答えを一つ見つける手続きを与えるわけです． 列挙アルゴリズムでは，名前の通り，答えを列挙するアルゴリズムについて考えています．

私は離散的な対象（グラフとか論理式とか集合族とか文字列とか）を研究しているわけですが， これらの対象で列挙問題を考えると答えの個数が \Omega(2^{n}) とか \Omega(n!) とかということは普通に起こります． それじゃあ全探索が最高に効率良いアルゴリズムなんですか？と言われるともやってしまいますので， 遅延という概念と出力依存型アルゴリズムという概念を作りました． 遅延は答えを出してから次の答え出すまでの時間で， 出力多項式時間アルゴリズムというと出力の個数も考慮して計算時間を決めましょうねという考え方です． もうちょっとちゃんというと，入力サイズ n と出力サイズ N を使って， O((n + N)^{c}) 時間で動作するアルゴリズムのことです．ここで c は定数ですね．

現状いろんな問題に対して多項式遅延があるか，出力多項式時間アルゴリズムがあるかが研究されているのですが，独断と偏見でなんで多項式遅延で解けるねん！とか 出力多項式時間で解けるのは流石におかしいだろみたいな問題を挙げておきます．

もうちょっと「網羅的」に眺めたい人はこちらもおすすめです．

kunihirowasa.github.io

なんで多項式遅延で解けるんだよ問題リスト

st パスと閉路

  • まずst パス列挙がまあ自分で思いつかなくはないが，少なくとも自分が学生の時に論文のタイトルを見ただけでは解けなかった．<\li>
  • 閉路については $st$ パスのアルゴリズムをサブルーチンに使って解けるんだけど，自分で思いつかんなぁという気持ち．

極大クリーク

  • 全ての元凶．こいつが解けてしまうせいで最適化周りと世界が大きく異なる．最適化の観点は近似も FPT も何も歯が立たないのに，なんで列挙だと超簡単なんだよ．

極小帰還集合（minimal feedback vertex set）

  • 歴史に残る偉業（個人の感想）．こいつのおかげで全列挙民が歓喜．Proximity search という新たな列挙技法ができたのは多分こいつのおかげ．

極小シュタイナー木（minimal Steiner tree）

  • $st$ パス列挙の一般化．連結性は辺に関するものは簡単めだけど，頂点に関する連結性は途端に難しくなる．やったら解けるんだけど，こいつが解けるのは許せん．

極小辺支配集合（minimal edge dominating set）

  • 頂点版の極小支配集合は全然わからない．解けたら10年くらいはチヤホヤされると思います（40年間の未解決問題）．辺にしたら急に多項式遅延で解けるんですが，意味がわからないですね．

極大誘導弦グラフ・極小フィルイン（maximal chordal induced subgraph・minimal fill-in）

  • 極大誘導弦グラフは解けるくせにその部分クラスの列挙にはこの手のテクニックが使えないので，「列挙問題もわけわかんない」ですねという気持ちにさせられます．
  • 極小フィルインは辺追加に対して弦グラフがいい構造を持っていなさそうに見えるのですが，なんかうまくいきます．このあたりは列挙というよりグラフ理論的な不思議（私の無知）な気はしています．

極大誘導二部グラフ

  • 実は列挙には出力多項式時間アルゴリズムを設計するためのテンプレ手法があります．Input-restricted problem とか supergraph technique とか X - Y + e method とか solution graph technique とか言われていますが大体全部一緒です．その技法でいくと，この問題は出力多項式時間ですらぱっと見はわからないのですが，proximity search を理解するとわりかし簡単に多項式遅延で解けます．わけがわからないですね．

なんで出力多項式時間で解けるんだよ問題リスト

平面上の全ての点を通る交差のない閉路

  • David Eppstein の論文．Surrounding polygon という別に列挙しやすい離散構造があってそっちを列挙すると実は個数が指数的にギャップないぜと示している．この手の「直接それは列挙できないんだけど，何かmeetな対象と個数差のギャップが多くないから全体として出力多項式時間で動作する」という例は potential maximal clique とこの論文しか知らない．他にあったら誰か教えてください．

潜在的極大クリーク（potential maximal clique）

  • 名前に「極大クリーク」とついていますね．私は愚かなので「極大クリーク列挙みたいなものだろ」と思い，勉強を始めましたが撃沈しました．定義としてはある頂点集合が潜在的極大クリークというのは，その頂点集合がバックとなる極小な木分解が存在するという定義です．極小セパレータと関係が深いようで，極小セパレータが列挙できていると潜在的極大クリークが列挙でき，これらの間には個数の差が多項式的にしか大きくないそうです．

マトロイドのサーキット

  • マトロイドのベースは良い性質あるけどサーキットはもうちょっと難しくあってほしい．一応サーキットによるマトロイドの定義もありますが．．．
  • いろんなマトロイドがあるけど，サーキット的に特徴付けされたものはあるんですかね？それがあるならまあ許せる．

列挙分野の重要な未解決問題

もはや列挙アルゴリズムの研究の話かもしれません．誰か解けたら論文書いてください．正座しながら読みます．

極小横断列挙

有界な凸多面体の単点列挙

  • 多面体の表現として，「この面で切る」という制約集合か，「端点集合」で表すかの2通りがある．この問題は前者から後者への変換．有界とはどの方向にも端点があるという意味．非有界は難しいが，有界は未解決．

返信により随時更新します．

何でお前そんな効率よく解けるんだよ問題リスト

みなさんアルゴリズムの勉強楽しいですよね（強制） アルゴリズムの勉強が楽しくないという場合，ここでこのブログは終了です．

さて色々すごいアルゴリズムは開発されているのですが，個人的に「許せん」という問題が多々あります． 「許せん」というのは個人的な感情なので説明が難しいのですが，こんな気持ちです． ある問題は $P \neq NP$ を信じた場合，多項式時間で解けないわけです．それと見た目はすっごい似てるのになぜか解けてしまう，そんなことがあったら気持ち悪い，みたいな気持ちです． 代表的なのは最大マッチングと最大独立点集合ですね． 辺と頂点，そんな変わらんだろと今でも割と思っています． Accidental Algorithmsというタイトルの論文もあるので，この感情はある程度一般的なのかとも思います．

最初はそんな感じで Twitter（現: X）にツイートしたわけですが，もうちょっと広い意味（この問題が線形時間で解けるのすごい）で問題がたくさん集まったので載せておきます． 問題が集まりすぎて Twitter の文字数制限超えそうだったので．．．

もし他にも問題候補がありましたら教えてください．随時更新します． 私の判断基準として，入力を制約すると解ける系の問題はちょっと NG 感があります．それを許すといくらでも増えてしまうので． ただ，完全に好みですが，現状平面グラフの完全マッチングだけは例外的に許しています．（平面性が意味わからん + 私が平面性に憧れがあるので） というわけで，以下がリストです．

なんで多項式時間で解けるんだよ問題リスト

  • 最大マッチング
  • 2 SAT
  • 線形計画問題
  • 素数判定
  • 劣モジュラ最小化
  • 頂点素 k-disjoint paths
  • 最大共通部分列（LCS）

諸々のグラフ認識問題（recognition）

  • 平面・弦・区間などなど．オタクにして良いならいくらでもあるが，とりあえずは幾何的に定義されるグラフの認識はなぜできるのか不思議でならない．
  • 幾何表現 -> グラフはいいが，逆はできんだろ．

重み付きグラフの最短路

  • 線形計画問題で定式化できるので解けるのはそれはそうなのですが，そもそも線形計画問題で定式化できるあたりが許せんポイントです．
  • 離散凸最適化という分野ではまた M 凸最適化とか L 凸最適化とか色々あって，その観点でも理解できるらしいんですが，憧れているだけで私は離散凸を何も理解していません．

数え上げ

  • 有向オイラー路

平面グラフの完全マッチング

  • これはクラスを制限しているのでこのリストの趣旨からすると NG だが，私の独断と偏見によって入れています．

何でそんなデータ構造作れんねんリスト

  • 平衡二分木

線形時間はおかしいだろ問題リスト

  • 接尾辞配列

Burrows-Wheeler Transform（BWT）

  • こいつは BWT で文字列を変換した後に run-length 圧縮すると文字列がよく縮むらしいのですが，この実験結果はまだ許していません．

番外編

いろんな問題解けすぎだろとなるグラフクラス

AT-free Graph

  • まず定義がなぞ．「asteroidal tripleってやつ禁止！」って定義だが，何をどう思ったら asteroidal triple なんてものを考えたくなるのか？そして実際に禁止すると最小支配集合が多項式時間で解けるらしいし，色々解きやすいらしい． <\li>

なんで決定可能なんだよ問題リスト

ベクトル加算系の到達可能性

  • 有向辺にベクトルがついている有向グラフを考える．初期状態として，頂点とベクトルが与えられる．ある辺を通ると現在の状態に辺のベクトルの値が足される．指定した頂点のベクトルのペアから，指定した頂点とベクトルのペアに到達できるか？という問題．wikipedia の図がわかりやすい．
  • 制約のない整数を扱っているので，状態数がいくらでも増えそう．いくらでもぐるぐる回れるので本質的に全部の状態が必要っぽいので「無限時間」かかりそう（無限時間はテクニカルタームではなく，私の気持ちを表しているだけです．）
  • 決定可能だと示されている．

列挙アルゴリズムの計算困難性について: 列挙問題と P vs NP

ここ数年，計算困難な列挙問題について興味が出てきました．自分の勉強がてら基礎的な部分をまとめてみます． まず列挙問題とはどんな問題かというと，ゆるくいうと，条件を満たすものを全て出力する問題です． 「もの」という曖昧な言葉があるので，列挙問題をちゃんと定義しようとすると以下のように定義します． 有限アルファベット \Sigma と， \Sigmaの要素の有限回の繰り返しで得られる全ての文字列 \Sigma^{\ast} に対し， R \subseteq \Sigma^{\ast} \times \Sigma^{\ast} という関係を考えます．*1 ここで列挙問題とは，文字列 x が与えられたとき， (x, y) \in R を満たす y を全て出力する問題と定義できます． 以降では (x, y) \in R を満たす y の集合を R(x) と略記させていただきます． まあ小難しく書きましたが，今回の話では条件を満たすものを全て出力する問題と思って大丈夫です．

この列挙問題を効率良く解きたいわけですが，よくあるアルゴリズムの世界のような多項式時間アルゴリズムは存在しないことが多いです． なぜなら，出力である R(x) の大きさが x の大きさの多項式サイズで抑えられないからです． それでは列挙アルゴリズム界隈ではどのようにアルゴリズムの計算効率を測るかというと，主に二つの流派があります． 一つはシンプルに入力サイズに対してどのくらい小さな指数になるかどうかということで計算時間を測ります． 主観ですが，こちらはアルゴリズムの研究でありながら，組合せ数学っぽさも感じますね． 列挙できるということはその構造の個数の上限がその計算時間で抑えられるわけなので，アルゴリズムを与えることはその構造の個数の上限を与えることになるわけです． もう一つは出力に依存する計算時間の解析です．出力サイズが入力サイズに対して指数的に大きくなるとはいえ，それは入力によって大きく変化するので，実際の出力サイズを計算時間に入れることで計算効率を評価しようという考え方ですね． このタイプのアルゴリズムなら出力が多くない入力に対しては効率よく動作します． この指標のもと，入力サイズと出力サイズの和に対して多項式時間で動作するアルゴリズムを出力多項式時間アルゴリズムと言います． 列挙アルゴリズムの世界では出力多項式時間アルゴリズムがある種の効率良いアルゴリズムというわけですね*2．

というわけで，列挙アルゴリズム分野ではそれぞれの列挙問題に対し， 出力多項式時間アルゴリズムがあるかどうかが理論的な研究トピックになります． そのようなアルゴリズムが構成できるときはアルゴリズムを作ってしまえば終わりなのですが，世の中そうあまくはなく，なかなか出力多項式時間アルゴリズムが構成できない場合があります． このような場合，自分の頭が悪いのか，問題が本質的に難しいのかなかなか分離することは難しいですね． 何の仮定も無しに「この列挙問題には出力多項式時間アルゴリズムが存在しない」と示ればそれはかっこいいのですが，なかなかそれも難しいです（というかどうやるのか私には想像もつきません） そのため，何らかの仮定をおいて「この列挙問題は難しい」と主張したいのですが，その際に使われる仮定が大きく分けて以下の二つです．

  1. 極小ヒッティングセット集合列挙に対して出力多項式時間アルゴリズムは存在しない*3．
  2. P \neq NP．

1については詳しく説明しないのですが，1の問題は入力サイズを n，出力サイズを N とすると，[tex: (n + N)^{o(\log (n + N))}] 時間のアルゴリズムが知られています． なので，個人的な感想が強く入りますが，この問題を「難しい」根拠にするのはちょっと弱いのでは？という気がしないでもないです． 一方， P \neq NP は証明されていないですが，まあ困難性を示す上ではある程度妥当と言って良い仮定かと思います． なので， P \neq NP を仮定して列挙問題の計算困難性を議論したいです． しかし，列挙問題の計算困難性と P \neq NP とは直感的には大きなギャップがあります． P \neq NP は決定問題（Yes か No を返す問題）の計算困難性の仮定である一方，列挙問題は全てを出力する問題なので，扱う問題が大きく異なります． なので，列挙問題的な難しさを含む決定問題を考えなくてはなりません．

そこで登場するのが別解問題です． 別解問題とは，列挙問題 \Pi の入力 x と R(x) の部分集合 S が与えられたとき， S = R(x) かどうかを判定する問題です． 以降では列挙問題 \Pi に対する別解問題を \Pi_{ano} と表記します． 要するに，今までの出力を見て，出力忘れがないかどうかをチェックする問題ですね． もし R(x) を出力する出力多項式時間アルゴリズムが存在するならば， \Pi_{ano}は多項式時間で解くことができます． ちょっとフォーマルに書くと以下のような主張ができます．

定理1 列挙問題 \Pi に対する出力多項式時間アルゴリズムが存在するならば，別解問題 \Pi_{ano} に対する多項式時間アルゴリズムが存在する．

証明: 列挙問題 \Pi を出力多項式時間で解くアルゴリズムを A とします． 出力多項式時間アルゴリズムの定義から，ある定数 c と dが存在し， A は入力 x に対し， d(|x| + |R(x)|)^c 時間以内に動作を終了します． ここで， A を d (|x| + |S|)^c 時間動作させます．このとき，アルゴリズムが停止すればアルゴリズムは R(x) を出力するので， S = R(x) かどうかは多項式時間でチェックできます． もしアルゴリズムが停止しない場合， |R(x)| > |S| ということがわかります．なので， S \neq R(x) になります．

定理1の対偶を取ると，「別解問題 \Pi_{ano}が多項式時間で解けないならば，列挙問題 \Pi は出力多項式時間で解けない」ということになります． ここで P \neq NP の仮定が有効になります． 別解問題は決定問題ですので， \Pi_{ano} が NP 完全であれば， P \neq NP の仮定では \Pi_{ano} を解く多項式時間アルゴリズムが存在しません． したがって，別解問題のNP困難性を示すことは元の列挙問題の計算困難性を示すことにつながるわけですね．

後の具体的な幾つかの別解問題の計算困難性の帰着についてはGW中にでも紹介しようと思います．

2025/05/05 更新

それでは別解問題が難しい問題をいくつか紹介しようと思います． まずは超一般的な以下の問題を考えます．

  • 入力: 集合 Uと，遺伝的性質を満たす集合族 S \subseteq 2^{U}， S 中で極大な部分集合の部分集合 T
  • 出力: T に含まれない極大部分集合は存在するか？

ある V \subseteq U が極大な部分集合というのは， V \in S かつ， V を真に含む任意の V' に対し， V' \notin S を満たすことを言います．また， S が遺伝的性質を満たすというのは， V \in S ならば， V の任意の部分集合は S に含まれることを言います． また，この問題は S が陽に与えられると S の大きさに対して多項式時間で簡単に解けてしまうので，今回はオラクルモデルを仮定します． つまり， U' \subseteq U が U' \in S かどうかのチェックをしてくれるなんらかの方法*4があると思ってください． T は本当に集合として与えられると思ってください． 今回の証明を理解すると，そういうオラクルがあったとしても，出力多項式回のオラクル呼び出しではこの問題が解けないことが示せます． もうちょっといろいろ知りたい方はこの論文にいろいろ書いてあります．

それでは本題に入ります．この問題を CNF-SAT から帰着します．今回は SAT についての説明は省略させていただきます． まず論理式 \varphi が与えられたとき，各変数 x に対して， U は xと \bar x を持ちます． なので， U の大きさは \varphi の2倍ですね．

次にオラクルを以下のように設計します．

  1. V がある変数 x に対応する x と \bar x を両方もたない場合， V \in S を返す．

  2. 1がなりたたず， V が y と \bar y を持つ変数 y が存在するとき， V \notin S を返す．

  3. 1と2 がなりたたないとき， V が変数 z を持つ場合 z に真を割り当て， \bar z を持つ場合偽を割り当てる．この割り当てで \varphi が充足される場合 V \in S を返す．充足されない場合 V \notin S を返す．

帰着の最後のパートとして T を定義します． T は各変数 x に対して， U \setminus {x, \bar x} からなる集合とします． これらの部分集合は条件 1 から S に含まれますし，条件 2 から極大であることがわかります． 証明の流れとしては， \varphi が充足可能である iff T に含まれない極大解が存在するということを示します． それではまず \varphi が充足可能であるならば T 以外の極大解が存在することを示します． これはそんなに難しくなく，充足割り当てに対応する部分集合 V を考えると，条件3から S に含まれ， T 中の部分集合は全て Vを包含しないので， T に含まれない極大解が存在します．

次に「 Tに含まれない極大解が存在するならば \varphi は充足可能」であることを示します． まず T に含まれない極大解を R とします． R が条件1を満たす場合， R を含む極大解が T に含まれるので， R の極大性に矛盾します，また， R は S に含まれるので条件2を満たしません．つまり， R は各変数 x に対し， x か \bar x のちょうどどちらか一方を含みます．したがって， R に基づき， x \in R ならば， x を真，そうでないならば x は偽と割り当てを定義することができます．最後に R は条件 3 を満たすので，この方法で得られた割り当ては \varphi を充足します． したがって， T 以外の別の極大解があるならば， \varphi は充足可能になります．

これでこの問題は出力多項式時間で解けないことが示せました． この問題はものすごく一般的だったのでもう少し普通？の問題についても考えてみましょう． 先ほど，極小ヒッティングセットの列挙は NP-hard ほどではないが難しいという紹介をしました． ここではヒッティングセットを一般化したハイパーグラフの性質 S を定義します．

  • 辺色付きハイパーグラフ H = (V, E_1, \ldots, E_k) に対し，ある色 i が存在し H_i = (V, E_i) において U が H_i のヒッティングセットになるならば U \in S とする．

上記で定義した性質 S に対し，極小な部分集合を列挙する問題を考えてみます． 直感的にはどこか一つの色で良いのでヒッティングセットになるような頂点集合の中で極小なものを列挙する問題ですね． この問題の別解問題も NP-hard であることを示すことができます．

  • 入力: 辺色付きハイパーグラフ H = (V, E_1, \ldots, E_k)と S の極小部分集合族の部分集合 U．
  • 出力: U に含まれない S の極小解は存在するか？

この問題は実はハイパーグラフではなく，単なるグラフに制約しても NP-hard であることが示せます．ご存じの方は多いかもしれないですが，ハイパーグラフではなくグラフの場合，ヒッティングセットは頂点被覆（vertex cover）と呼ばれます．

というわけでいつものように 3 SAT からこの別解問題への帰着を考えます． 知っている人は SAT から最小頂点被覆への帰着を想像してもらえるとかなり近いです． まずは各変数 x に対し，2頂点からなるパスを追加し，各節 C_i = ( \ell^{\ i}_1 \ell^{\ i}_2 \ell^{\ i}_3) に対し，三角形を追加します． そして，パスの単点を x と \bar x としたとき， \ell^{\ i}_j が x に対応するとき，辺 \{x, \ell^{\ i}_j\} を追加し， \bar x に対応するときには \{\bar x, \ell^{\ i}_j \} を追加します．このとき追加された辺の色は全て同じだと思ってください． ここまでは最小頂点被覆の NP-hardness の証明と全く同じです．ここまでに追加した辺には色 0 がついていると思ってください． 想像しにくい人はこのスライドの4ページとかを見ると帰着が載っています．

さらに，変数 x_k に対応する各パス P_k = (x_k, \bar x_k) の両端点に対し二つの頂点 u_k と v_k を追加し，色 k で辺 \{x_k, v_k\}, \{\bar x_k, u_k\} を追加します． 最後に，各節 C_i に対し，3つの頂点 c_1, c_2, c_3 を追加し色 n + i の辺 \{c_1, \ell^{\ i}_1\}, \{c_2, \ell^{\ i}_2\}, \{c_3, \ell^{\ i}_3\} を追加します． n は変数の個数です． これで帰着は終わりです． この帰着において，色 0 のグラフに対する極小解が存在することと 3 SAT が充足することが等しくなります．

大雑把ですが証明は以下のように行います． 色 0 以外の色においては極小解が定数個しかないので割愛します． 色 0 の極小解がある場合，各パスのどちらか一方の頂点しか取れないし，両方取らないと頂点被覆であることに矛盾します． また，節に対応する三角形については，三角形であるということは少なくとも二つの頂点は取らないと頂点被覆にできません． さらに，全ての頂点を取ってしまうと色 0 以外の色の頂点被覆になってしまいます．したがって，全ての節において，少なくとも一つの変数は充足されないと色 0 において極小解になりません． なので色 0 の極小解は \varphi を充足する変数割り当てと一対一に対応するわけです．

他にも複数文字列から極大共通部分列の別解問題やグラフのセパレータに関する別解問題が難しかったりと，別解問題の困難性はわからないことだらけですので興味ある人は考えてみてください．

*1: \ast の表示が気持ち悪くてすみません．．．

*2:とはいえ，出力サイズは入力サイズに対して指数に大きいことが経験的に多いので，出力サイズに対して2乗や3乗という時間は嫌な気持ちになります．なので，理論的には出力サイズに対して線形時間の列挙アルゴリズムが存在するかも興味が持たれているトピックです．

*3:ハイパーグラフ H = (V, E) において，任意のハイパー辺が頂点集合 U の要素を1つ以上持つとき， U をヒッティングセットと言います．そして，ヒッティングセット U に真に包含されるヒッティングセットが存在しないとき， U を極小ヒッティングセットと言います．この列挙問題はそのような頂点集合を列挙する問題です．極小横断列挙とか単調論理関数双対化とか（ハイパーグラフ上の）極大独立点集合列挙とか極小集合被覆列挙とかの問題もこの問題と等価です

*4:こういうなんらかの答えを教えてくれる道具をオラクルと言います．

近似アルゴリズムのお話し: Baker's technique

今年もデータ構造とアルゴリズムアドベントカレンダーの季節になってきました．これはカレンダー12日目の記事ですね．個人的な話ですが，去年度にようやく長い長い学生生活を終えたので，今年は隣の分野くらいのことをちゃんと勉強してみたいなぁと思い，いろいろ漁って勉強しました．TLの皆さんにはいろんな有用情報をいただいてありがとうございました！「このツイートしたら誰かいい情報教えてくれないかなぁ」と期待してツイートしたことが何度もありました．

そんなこんなで興味あったけどちゃんと勉強していなかったマトロイド，近似アルゴリズム，乱択アルゴリズムあたりをちゃんと本買って読んでみるか〜と思い，最初の1章とそれ以外を1つくらいは読んで，完全に理解しました．その中で，近似アルゴリズムが一番わかった感が強いので，自分の復習も兼ねて，近似アルゴリズムでよく使われるテクニックを1つ紹介しようかと思います．ちなみに僕は近似アルゴリズムを[1]で勉強して，今回は[2]の論文のテクニックを紹介します．

今回紹介するテクニックは1994年に発明されたBaker's techniqueとよばれるアルゴリズム構築技法です．これは入力が平面グラフのときに，最大独立点集合問題や，最小頂点被覆問題，最小支配集合問題といったNP-完全な問題に対し，PTAS（polynomial time approximation schem）を与えるアルゴリズム構築技法です．今の一文で未定義用語が5つくらい出ましたね．問題の名前はいいとしても，平面グラフと，NP-完全，PTASあたりは説明が必要かと思います．なので，次にそれらの用語の説明を簡単にします．

用語と今回の目標の説明

今回出てくる用語について簡単に定義します．正確でない定義も多々ありますので，正確な定義が知りたい方は申し訳ないですが，参考文献の方を見てください．

  • 平面グラフ: 平面に辺の交差がなく描けるグラフのことです．グリッドなんかは平面グラフですね！正確には平面的グラフという気がしますが，今回は平面グラフと読んでしまいます．これはplanar graphとplane graphは実はちょっと違うという話と関係あると思っています．
  • NP-完全問題: これは正確な定義がかなりややこしいので，ここではかなり多くの嘘を含みますが，多項式時間で解けないと信じられている問題の集合くらいに思ってくれれば大丈夫だと思います（プロの方が見ていたら生暖かい目で見逃してください）．
  • PTAS: これは近似アルゴリズム分野の用語で，次のような条件を満たすアルゴリズムをPTASとよびます．最大化問題$\Pi$に対し，入力$I$とエラーパラメータ$\epsilon$（$\epsilon$は定数とみなす）が与えられたとき，最適解の値を$OPT$とすると，$(1 - \epsilon)OPT$を多項式時間で計算するアルゴリズム．

最小化問題に対するPTASは$(1-\epsilon)$が$(1 + \epsilon)$になります．計算時間の具体例としては，$O(|I|^{1/\epsilon})$時間と言った計算時間です．この時間で動作するアルゴリズムは$\epsilon$が定数なので，多項式時間で動作するとみなします．このとき，特に$|I|$と$1/\epsilon$の両方に関して多項式時間で動作するアルゴリズムはFPTAS（fully polynomial time approximation scheme）とよばれます．ナップサック問題なんかはFPTASを持つ問題の典型ですね．なので，この話を最大独立点集合問題を例に当てはめると，入力$I$が平面グラフ$G$で，エラーパラメータ$\epsilon$が与えられたときに，PTASを達成するアルゴリズムを与えます *1 *2

ちょっとした注意

この記事で紹介する方法では何度か木幅というグラフのパラメータを計算する必要があります．しかし，僕は実は木幅の厳密計算を理解していないので，今回の記事に書いてある方法だけでは近似アルゴリズムを作れません．しかし，入力グラフの木幅の値 $tw$ が$\epsilon$ を定数としたときに，定数であることが示せることと，定数 $k$ に対して，幅が $k$ 以下の木分解を計算する or 幅が $k$ 以上だと返すのは「線形時間」[6] *3でできるので，木幅は線形時間で計算可能だと思って記事を書いています．本音を言うとちゃんと元論文を読めばグラフの性質を使って線形時間で木幅がもっと簡単に厳密計算できそうに見えるのですが，まだそこまで理解していないです．ごめんなさい*4．

Baker's techniqueの概要

Baker's techniqueは現代の知識，特に木幅DPの知識を持ってみると実はすごい簡単なテクニックです．木幅に関するDPはきっと15日のゆらふなさんが書いてくれると思うので，今回はDPの詳細は省略しますが，木幅の定義は与えます．

大雑把にいうとBaker's techniqueは次のようなアルゴリズム構成法です．平面グラフ$G$の任意の頂点$v$を始点とし，$v$からの距離によって頂点を $V_0 = \{ v \}, V_1 , \ldots, V_{ n-1 } $ に頂点を分割します．この分割において，整数$j < k$に対し，$\bigcup_{ 0 \le i \le n/k } V_{ ik + j }$を削除します．直感的に言うと，距離 $k$ ごとにその距離を持つ頂点を全部消すと言う操作です．すると，グラフがいくつかの連結成分に分解されるのですが，実はこれらの連結成分は$k$-outerplanar graphと言い，$k$ が定数ならば，多くの難しい問題が簡単に解けがちなグラフになります．実際，$k$-outerplanar graph上では最大独立点集合は線形時間で計算できます．なので，このそれぞれの$k$-outerplanar graph上で，最大独立点集合を計算し，その和集合である独立点集合は実は良い近似比を達成すると言うテクニックです．そして，この $k$ の値を$1/\epsilon$ に設定すると近似比が $(1-\epsilon)OPT$ になり，計算時間も$n$ と定数$1/\epsilon$ に対して多項式時間になるので，PTASを達成します．

$k$-outerplanar graph 上での最大独立点集合問題

次に $k$-outerplanar graph の定義と，なぜ $k$-outerplanar graph上なら最大独立点集合が線形時間で解けるかを説明します．まずは定義からです．$k = 1$の時，つまり $1$-outerplanar graphはouterplanar graphともよばれ，平面描画するときに，全ての頂点が外面と接する様に平面描画できる平面グラフです．さらに，$k$-outerplanar graphとは平面描画したときに，外面と接する頂点を削除するという操作をすると $k - 1$ -outerplanar graphになるグラフです．$k$-outerplanar graphの具体例は次のようなグラフです．

f:id:chocobaby-aporo:20201210141834j:plain

このグラフだと外面に接する頂点削除を2回繰り返すとグラフが空にできるので，$2$-outerplanar graphです．

次に，平面グラフと $k$-outerplanar graph の関係を考えます． まず，平面グラフ中の頂点 $v$ に対し，先程の距離ごとに頂点集合を分割するルールを適用すると次のようになります．以下の例では 中心の頂点 $v$ を 頂点1にしています．

f:id:chocobaby-aporo:20201212190947j:plain

今回は$k=2$，つまり，$v$ からの距離が偶数の頂点を消した時の例を描いてみましたが，$k$を一般の場合にしてもだいたいこのように，中心から同心円状に頂点がのび，階層が$k$回に1回削除されるという構造になります．これをみると，削除されなかった頂点からなるグラフは，平面グラフの平面描画を考えると，外面に接する頂点削除を$k$回行うと空にできるので，これは$k$-outerpalar graphになります．

次に，$k$-outerplanar graphの木幅について考えます．木幅のお話は結構有名なので，他のブログにもありますね．

mizuwater0.hatenablog.com

それと日本語wikiもあります．

ja.wikipedia.org

あと，電気通信大学の授業もおすすめです．

http://dopal.cs.uec.ac.jp/okamotoy/lect/2016/treewidth/handout06.pdf

せっかくなので，電通大の授業スライドから定義を借りてくると，木分解の定義は次のようになります．

グラフ $G = (V, E)$ に対して，次の木 $\mathcal T$ を$G$ の木分解という

  • $\mathcal T$ のノードは$V$の部分集合
  • 各辺 $\set{u, v} \in E$に対し， $\set{u, v} \subseteq X$となるノード$X$が存在する．
  • 各頂点 $v \in V$ に対し， $\mathcal T$ で $v$を含むノード$X$からなる誘導部分グラフは木になる．

具体例はwikiとか授業スライドを見るとわかりやすいと思います． ここで，ノード$X$の頂点数の最大値を$\mathcal T$の幅といいます．この条件を満たす分解はたくさんある（自明な木分解は$\mathcal T$が1ノードからなる木で，そのノードが全ての頂点を含む時）のですが，幅が最小である木分解の幅を$G$の木幅といいます． そして，実は$k$-outerplanarの木幅は $3k-1$ 以下であることが知られています[3]．

木幅が小さいグラフというのはめちゃくちゃ嬉しい性質が知られています．それはCourcelleの定理と呼ばれているのですが，次のような激ツヨ定理が知られています．

  • 入力グラフ $G$ 木幅が定数であり，MSO（monadic second order logic）式 $\phi(X)$ が与えられた時，$\phi(X)$ を満たす要素数最大の $X$ は線形時間で発見できる．*5

MSOについてはここを参考にするといい感じです*6． 独立点集合は次のMSO式で書くことができます．

$\phi(X) = \forall u \in X( \forall v \in X( \set{u, v} \not\in E)$

この「MSOで記述できれば線形時間で解ける」という結果は激ムズなんですが，個々にアルゴリズムを作るのはそんなに難しくないことが多いです． きっとゆらふなさんの記事を読めば解けるようになると信じています． 大雑把には木分解の木があるので，その木の葉っぱからDPをするのですが，1ノードごとに状態数が$2^{k}$状態あるのでそれを全部覚えながらDPする感じです．なので，詳細は省きますが，独立点集合なら（確か） $O(2^{k} k^{2} n)$ 時間で解けます*7．今木幅は$3k-1$以下なので，$k = 1/\epsilon$に設定すると，この計算時間は $O(8^{1/\epsilon} (1/\epsilon)^{2} n)$ 時間になりますね．これをそれぞれの連結成分ごとに計算するので，総和は同じ計算時間で抑えられます．最後に，どの距離の頂点集合を削除するかが $k$ 通りあるので，$k = 1/\epsilon$回繰り返すため，全体の計算時間は $O(8^{1/\epsilon} (1/\epsilon)^{3} n)$ になります（注意: 木分解を計算する時間は考慮に入れていないです．）．これで計算時間はPTASの定義を満たしていますね！

あとは今計算した独立点集合の和集合がちゃんとサイズ$(1 - \epsilon)OPT$ 以上を達成するかどうかという近似比についての議論します．

アルゴリズムの近似比の解析

まずアルゴリズムの近似比の解析のために$S$を$G$中の最大独立点集合とします．今，グラフの分割をいくつか試しているので，分割の中で最も$| S \cap \bigcup_{0 \le i \le n/k}V_{ik + j}|$が小さい$j$ではサイズが$|S|/k$以下になります．実際にどの$j$がサイズを最小にするかはわからないのですが，これは全通り試しても$k$通りしかないため，これは全通り試し，サイズが最大な独立点集合を出力すればサイズを最大にする $j$ は見つけられます． したがって，得られる独立点集合のサイズは$(1 - 1/k) OPT$となります．よって，$k = 1/\epsilon$とすれば，近似比は$(1 - \epsilon)$を達成します．

Baker's techinqueの発展

平面グラフに対する効率良いアルゴリズムはかなり昔から研究されていて，グラフアルゴリズムの中心的な分野と言っても良いと思います．正直怖いのであまり手を出したくなかったのですが，これは意外と簡単だったので，ちょっと興味が出てきました．Baker's techniqueも90年代のテクニックだし， 平面グラフ上のアルゴリズムというメジャーなトピックなので，いろいろ発展系が研究されている様です．この辺りは本当によく知らないのですが，グラフの平面さを表すcrossing number（平面描画した時の辺の最小交差数）あたりでは研究がある様です[4]．それと風の噂によると，Bidimensionalityというのも発展系っぽいというのを聞きました[5]．なんか$k \times k$のグリッドグラフをマイナーとして含まないようなグラフに対するDPっぽいです．（あんまりわかっていない．）

なんかBaker's techniqueは結構簡単なテクニックかとおもっていたのですが，こうやって書いてみるとそれなりにいろんな知識が必要ですね．

参考文献

[1] Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013.
[2] Baker, Brenda S. "Approximation algorithms for NP-complete problems on planar graphs." Journal of the ACM (JACM) 41.1 (1994): 153-180. [3] Bodlaender, Hans L. "A partial k-arboretum of graphs with bounded treewidth." Theoretical computer science 209.1-2 (1998): 1-45.
[4] Grigoriev, Alexander, and Hans L. Bodlaender. "Algorithms for graphs embeddable with few crossings per edge." Algorithmica 49.1 (2007): 1-11.
[5] Cygan, Marek, et al. Parameterized algorithms. Vol. 4. No. 8. Cham: Springer, 2015.
[6] Bodlaender, Hans L. "A linear-time algorithm for finding tree-decompositions of small treewidth." SIAM Journal on computing 25.6 (1996): 1305-1317.

*1:元論文は $O(8^{1/\epsilon} (n + m) )$ で，僕の今回のアルゴリズムは $O(2^{2^{1/\epsilon}} (1/\epsilon)^{3} n)$ くらいなので，めっちゃ負けていますが，PTASにはなります．

*2:木幅計算パートを無視すると，$O(8^{1/\epsilon} (1/\epsilon)^{3} n)$ になります．

*3:定数項がえげつないです．ざっと見積もっても $2^{2^{k}}$ は軽くあります

*4:PTASを与えると言う結果には矛盾しないので許してください！

*5:記述が間違っていたらごめんなさい

*6:この授業スライドは他のトピックも非常に面白いので，おすすめです．僕はマトロイドも結構ここのスライドで勉強しました．

*7:$k^{2}$ の部分が自信ないですが，$poly(k)$ なのは間違い無いです．

オレンジグラフの別解（TLEしました．）

昔昔にオレンジグラフという問題が出ていましたね． atcoder.jp

これはどういう問題かというと，グラフが与えられるので，極大な部分二部グラフ（これ以上二部性を保証しながら辺追加ができない部分二部グラフ）の列挙が想定解法なのですが，計算時間が $O(m 2^n)$ 時間と指数的に時間がかかります．

列挙アルゴリズムではこのように指数時間かかるのはそもそも答えの数が指数個あるので，ある種しょうがないのですが，この答えの個数というバウンドを使ってしまうと面白みがなくなる問題もいろいろあります．例えば，線分の集合が与えられた時に，その交点を列挙しろという問題では，$n$を線分の個数とすると，ナイーブアルゴリズムは $O(n^2)$ 時間で動作します．しかも，最悪時，交点の個数は $O(n^2)$ なので，このナイーブアルゴリズムが最適になってしまいます．なんかこれでは面白くないということで，答えの個数を$M^{}$とおき，$M^{}$と$n$を使って計算量を見積もるというアルゴリズムが開発されてきました．交点列挙なら，確か $O( ( n+M ) \log n)$で列挙できたと思います（自信ない）．このように解の個数と入力サイズの2つを用いて計算量が抑えられるアルゴリズムを出力依存型アルゴリズム（Output sensitive algorithm）と言います．

ここで自然な疑問として，今回のオレンジグラフもOutput sensitiveに解けないのか？という疑問があります．実はこれは解くことができます！具体的には今回実装したアルゴリズムは $O(M m^2)$ 時間，$O(M m)$領域のアルゴリズムになっています．ちなみに本当のことを言うと実装をサボるために時間が$O(M m^2 \alpha(2n, n) )$ 時間になっています． $\alpha(2n, n)$ はいつも通りunion findの計算量です．noshi91さん，実装のアドバイスありがとうございました！．

noshi91.hatenablog.com

正当性の証明は結構めんどくさいのですが，アルゴリズムはめっちゃ簡単です．正当性に関する解説はここですね．

qiita.com

ざっくり証明のアイディアを説明すると，こんな感じです．基本的に，極大部分二部グラフ（MB）から別のMBを作るのはそんなに難しくなく，たくさん答えを見つけることはできます．具体的にはあるMBを1つ見つけてから，そのMBに含まれない辺1つからなる部分グラフは二部グラフなので，それに適当に辺を追加し，MBを作れば別なMBを作ることができます．なので，問題は全てのMBを出力できているかです．これを証明するためには，MBとMBの間に距離のような指標を定義してあげるというアイディアが結構うまくいきます．これは何をしたいかというと，MBを1つの頂点だと思い，MBから別のMBを作るルールを有向辺だと思った時にできるグラフを強連結にしたいという思想から来ています．もしこのルールで作られたグラフが強連結なら，適当にBFSやDFSすればMBが列挙できますね．ここで，強連結の定義を思い出すと，「任意の頂点ペア $u$ と $v$ について $u$-$v$ パスが存在する」でしたね．このパスの存在性を示すために， $u$ から $v$ に到達可能であることを示す必要があります．そのため， 今のMBから別のMB'に到達可能ということを示すため，MBとMB'の間にある指標を定義し，その指標を小さく or 大きくするMBに到達できるということを示すというのが一つの戦略になります．いろいろ言いましたが，最後に結論だけ言ってしまうと，MBの頂点ID最小の頂点からBFS順に辺を並べて，その辺の列のprefixをどんどん伸ばしていくということをやっていけば必ず欲しい解MB'に到達できるよ〜というお話しです．以上が証明の気分でした．

具体的なアルゴリズムは以下のとおりです．

  • 適当にMBを求める．
  • 得られたMBをキューに突っ込み，キューが空になるまで以下を繰り返す．
    • キューからMBを一つ取り出す．
    • MBに含まれない辺$e = \set{x, y}$を選択し，MBから$x$に接続した辺を全て削除して得られるMBxと$y$に接続する辺を全て削除して得られるMByを作る．
    • MBxとMByに適当に辺を追加して極大な二部グラフを作る．得られた極大二部グラフがまだ出力していない解ならば，キューに突っ込む．

というわけで意気揚々とAtCoderさんに投げたのですが，TLEしました！（悲しいね）．僕が思ったより答えの数が多かったようで，多項式倍の部分で勝てなかったようです．．． 結構このアルゴリズムの実装は楽チンで，union find partとデータの受け取りとか除くと大体50行くらいでかける感じでした．

以下ソースコードです．

#include<iostream>
#include<queue>
#include<set>
class edge{
public:
    int x, y;
};
class UnionFind{
public:
  UnionFind();
  UnionFind(int _n){init(_n);}
  void init(int _n){
    n = _n;
    if(rank.size() == 0)rank.resize(n), parent.resize(n);
      for (int i = 0; i < n; i++) {
      rank[i] = 0;
      parent[i] = i;
    }
  }
  int find(int x){
    if(x == parent[x])return x;
    else return parent[x] = find(parent[x]);
  }
  
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      parent[x] = y;
    }else{
      parent[y] = x;
      if(rank[x] == rank[y])rank[x]++;
    }
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
  int size(){
    int res = 0;
    for (int i = 0; i < n; i++) {
      if(parent[i] == i)res++;
    }
    return res;
  }
private:
  int n;
  std::vector<int> rank, parent;
};

UnionFind uf(40);
 
std::vector<int> Maximize(std::vector<edge> &G, int n, std::vector<int> &subg){
    uf.init(2*n);
    for(int i = 0; i < (int)G.size(); i++) {
      int x = G[i].x, y = G[i].y;
      if(subg[i] == 1) uf.unite(x+n, y), uf.unite(x, y+n);
    }
    for(int i = 0; i < (int)G.size(); i++) {
      int x = G[i].x, y = G[i].y;
      if(subg[i] == 0){
          subg[i] = 1;
          if(not uf.same(x+n, y+n)) uf.unite(x+n, y), uf.unite(x, y+n);
          else subg[i] = 0;
      }
  }
  return subg;
}
 
void EnumerateNeighborhoods(std::vector<edge> &G, std::vector<int> &subg, int a, int n, std::set<std::vector<int> > &ans, std::queue<std::vector<int> > &que){
    std::vector<int> S = subg;
    for(int i = 0; i < (int)G.size(); i++) {
        if(G[i].x == G[a].x or G[i].y == G[a].x)S[i] = 0;
    }
    S[a] = 1;    
    Maximize(G, n, S);
    if(ans.find(S) == ans.end()){
        ans.insert(S);
        que.push(S);
    }
 
    S = subg;
    for(int i = 0; i < (int)G.size(); i++) {
        if(G[i].x == G[a].y or G[i].y == G[a].y)S[i] = 0;
    }
    S[a] = 1;
    Maximize(G, n, S);
    if(ans.find(S) == ans.end()){
        ans.insert(S);
        que.push(S);
    }
}
 
int main(){
    int n, m;
    std::cin >> n >> m;    
    std::vector<edge> G(m);
    std::set<std::vector<int> > ans;
    for(int i = 0; i < m; i++) {
        int from, to;
        std::cin >> from >> to;
        G[i].x = --from, G[i].y = --to;
    }
    std::vector<int> subg(m, 0);
    Maximize(G, n, subg);
    std::queue<std::vector<int> > que;
    que.push(subg);
    ans.insert(subg);
    while(not que.empty()){
        subg = que.front();
        que.pop();
        for(int i = 0; i < m; i++) if(subg[i] == 0) EnumerateNeighborhoods(G, subg, i, n, ans, que);
    }
    std::cout << ans.size() << std::endl;
}

辞書順幅優先探索Lex BFS（Chordal Graph 5回）

この記事はデータ構造とアルゴリズムアドベントカレンダー 2018の19日目の記事です．

qiita.com

とりあえず懺悔します．遅れて申し訳ありません．

データ構造とアルゴリズムアドベントカレンダーで列挙とかの話をしようかなぁとか思ったのですが，書くのが大変だったのと， これ読みそうな人類って誰だ？という気持ちになったので，ちょっと違う話をしようと思います． なので，今回は探索アルゴリズムの基本とも言える幅優先探索の亜種である辞書順幅優先探索について書いていきます． （ちなみにこの記事は1年くらい更新していなかったChordal Graphの第5回も兼ねています．） 今回のネタ本はこんな感じです． Graph Classes: A Survey Algorithmic Graph Theory and Perfect Graphs

グラフ探索アルゴリズム

有名なグラフ探索アルゴリズムとして幅優先探索（breadth first search, BFS）と深さ優先探索（depth first search）があります． これらは（多分）情報系の大学に行くと2年生か3年生くらいに習って，多分授業で実装をする機会もあるくらい有名なアルゴリズムだと思います． しかも，これらのアルゴリズムはグラフ探索だけでなく，メモリと時間を気にしさえしなければ（指数時間，指数メモリを許せば）いろんな問題がこの2つの探索で解くことができます． グラフ探索っぽくない幅優先探索の使い方でよくあるのは次のような問題ですかね？

  • 15パズルを完成させる最短手数を求めよ

これらのグラフ探索アルゴリズムは簡単ですが，実は使い勝手が良く，いろんな問題がDFSやBFSっぽい考えで解くことができます．

  • グラフ上の最短経路問題: BFS
  • グラフ上の最短閉路問題: BFS
  • グラフの平面性判定: DFS
  • 関節点や橋の列挙: DFS
  • 有向グラフの強連結成分分解: DFS

（何か他にいい例を知っている方がいたら教えてください．．．）

そんなBFS，DFSの中で，今回は少し変わったBFSであるLex BFS（Lexicographical BFS）を紹介しようと思います． これはほぼBFSと同じなんですが，キューに次の頂点を追加する際，少しだけ追加の順序が異なります． 通常のグラフ探索のBFSする場合，ある頂点$v$をみて，$v$の隣接頂点をキューに追加する順番は適当で良いのですが， Lex BFSではちょっと頭を使ってキュー中の順序を管理します．

Lex BFS

Lex BFSの疑似コードは次のようになります．まずは前提として，$G$中の任意の頂点$v$は1つの文字列$S_v$を持っていると思ってください． 初期値として$S_v = \emptyset$とします．また，以下では数字を文字のように扱います．文字列は数字の列だと思ってください．

$LexBFS(G)$ 入力: グラフ$G$，頂点数 $n$ ，辺数 $ m $

  1. $G$の任意の頂点$v$は文字列$S_v = \emptyset$を持ちます．
  2. $G$中の頂点で辞書順最大の文字列を持つ頂点$v$を選ぶ．（もし辞書順最大が複数ある時はその中から任意に選んで良い．）
  3. $v$の隣接頂点$u$が持つ$S_u$の末尾に文字$n$を追加します．
  4. $n$を1つ小さくして，2行目の処理に飛びます．

実行例はこんな感じです．

f:id:chocobaby-aporo:20181225010348g:plain

実はLexBFSはコーディングを頑張ると線形時間で実装できます． 実装をwikiを見るとなんとなくわかると思います． 簡単にいうとリストと$n$個の番兵的なものを使うと実装できると思います．

Lex BFSを用いたグラフのChordality判定

実はこのLexBFSを使ってグラフがchordal graphかどうかの判定問題が解けます． 方法は簡単で，Lex BFSをして求めた頂点の探索順の逆順がPerfect elimination ordering (PEO)かどうかを確かめるだけです． 実際に(8, 7, 2, 5, 12, 10, 11, 4, 3, 9, 6)の順序を逆にした(6, 9, 3, 4, 11, 10, 12, 5, 2, 7, 8) は入力グラフ$G$のPEOになっています． ここで，PEOの定義は次の通りです．頂点順序$σ = (v_1, v_2, ..., v_n)$が任意の$v_i$に対して，$v_i$から$v_n$を用いて作る誘導部分グラフ$G'$の中で$v_i$がsimplicial vertexであるとき，$σ$をPEOと言います．また，ある頂点$v$がsimplicial vertexであるとは，$v$とその隣接頂点からなる誘導部分グラフがクリークになることを言います．

では，この順序がきちんとPEOになっていることを証明してみます． と思ったのですが，本当に申し訳ありませんが，証明はもう少し後に公開します． （完全に理解していない + 時間が足りない）

　LexBFSの他の使い道

LexBFSは他にも使い道があって，次のグラフクラスの認識にも使えるようです．

  • HHD-free graph
  • distance-hereditary graph
  • interval graph
  • co graph graph

この辺りのこともいつか書いて見たいですね．

木の同型性判定のお話

この記事は文字列アドベントカレンダー5日目の記事です．

qiita.com

はじめに

文字列Advent Calendarと言いつつ，木について書いていこうかなと思います． まあ，文字列ガチ勢から見れば，根付き木は実質文字列なので，このCalendarで書いてもみんな喜んでくれると信じています． あと，実際ここで紹介する手法でも木を文字列に変換してから色々やって，木の同型性を判定します．

紹介内容

今回紹介するのはタイトル等にもあるように，木の同型性判定問題を線形時間で解くアルゴリズムの紹介をします． 木のお話をする前にグラフの同型性判定問題について説明します．グラフの同型性判定問題とは，2つのグラフ$G$と$H$が与えられた時，$G$と$H$の頂点間に辺の有る無し関係を変えないような頂点の対応付けがありますか？というYes/No問題に答える問題です． 木の同型性判定問題とは，この入力グラフ$G$を木に限定した場合にどうやったら解けるの？という問題です．

根付き木の同型性判定問題

いきなり木に限定するとよくわからないので，根付き木の同型性判定から紹介しましょう． 以下この節の説明では木といったら根付き木と思ってください． この内容はこのPDFと このスライドの内容です． また，スライド中のAHUアルゴリズムは[1]の本の内容です． 僕は本が手に入らなかったので，スライドで勉強しました，

ここでは文字列ガチ勢の人々が大好き（と思われる）テクニックである，木の文字列への変換を使います． 木の同型性判定のアルゴリズムの概要をざっくり説明すると，木をあるルールで文字列にして，

  • 変換後の2つの文字列が同じである $\iff$ 2つの木が同型である

という変換ルールを与えるというアルゴリズムです． 木を括弧列に変換する方法は簡単で，次のように変換します．

f:id:chocobaby-aporo:20171205170442j:plain

これは葉を"()"とし，中間ノードは子供を1列に並べて両端を"("と")"でまとめるといった操作で 木を文字列に変換します．中間ノードに対応する文字列を生成する場合，子供の文字列をソート順で 連結するようにします．結論から言うと， 実はこの文字列が一致していることと木が同型であることが同値な条件になっています． 以降はこの正当性についてて見ていきます． 正当性のきちんとした証明を見ようと上記のスライドと資料を見たら"明らかである．"，"証明は簡単だ"と書かれていました． 悲しい．．． ゆるふわに証明らしき物を考えてみます． まずは

*　括弧列が同じである $\to$ 木が同型である．

ですが，こちらは問題なく正しそうに見えます．次に

  • 木が同型である　$\to$ 括弧列が同じである．

を考えてみます． これは正しそうで，帰納的に考えると， 高さ$0$の木は自明に同型ならば括弧列が同じになります． 高さ$k$以下の木は正しく括弧列が同じくなるとし， 高さ$k + 1$の木を考えます． この時，根を親に持つ頂点以下のそれぞれの部分木を考えて，それらの部分木を文字列に変換すると， それぞれの部分木は高さ$k$以下なので，木が同型ならば括弧列が同じになります． その括弧列をソートしたとすると，元の木の文字列も一意に定まり， 木が同型ならば括弧列が同じになります． こんな感じに帰納法的に考えるとこの条件が正しい気がして来ます．

次にこのアルゴリズム（以降ではAHUアルゴリズムと言います．これはAho，Hopcroft，Ullmanの頭文字から来ています．） の時間計算量を考えます．これは最悪ケース各ノード $O(n)$ 文字持つことになるので $O(n2)$ 時間アルゴリズムです． AHUアルゴリズムを線形時間になるように改良します．

と思いましたが，時間の関係上とりあえず割愛します．（気が向いたら更新しときます．） 雰囲気で説明すると下の図のように毎回文字列を整数値1つに書き換えます．

f:id:chocobaby-aporo:20171205203500j:plain

木の同型性判定

先ほど与えた根付き木の同型性判定問題を解くアルゴリズムを使って木の同型性判定を解きましょう． ここで，グラフには中心という頂点が存在します． 中心の説明の前にグラフの半径(radius)について定義します． ここで，$G$中の任意の頂点$u$とした時，$v, u$間の距離を$d(u, v)$と定義します． グラフ$G$中の$v$が$G$の中心であるとは，$max_{u \in V}(d(u, v))$が最小な頂点$v$を$G$の中心と言います． つまり，どんなに遠くに行こうとしても最短パスしか通れないならあんまり遠くに行けない頂点ということです．

そして木が同型なので，

  • 木が同型である $\to$ $G$の中心は$H$の中心に対応付けられる

ということがわかります． したがって，同型ならば少なくとも中心は等しくなります． この性質より，根無し木を，木の中心同士を根と思って 根付き木にとし，根付き木の同型性判定アルゴリズムを使えば終わりです． また，木には中心が高々2つしか存在しないので，定数回の AHUアルゴリズムの適用で判定ができます． したがって根無し木も $O(n)$ 時間で同型性が判定可能です．

非常にゆるゆるで申し訳ないですが， こんな感じで木の同型性判定が行えます．

僕は$O(n \log n)$の雑実装でこんな感じで実装しました．

参考文献

  1. Aho, Alfred V., and John E. Hopcroft. The design and analysis of computer algorithms. Pearson Education India, 1974.