DAGのトポロジカルソートのうち最適なものを見つけたい

DAG (Directed acyclic graph) のトポロジカルソートは一般にΟ(V!)通りありますが、その中で特定の評価関数を最小にするものを見つけたい、という問題群を考えています。

最適化コンパイラを作るときに出てきた問題やコードゴルフに関連する問題も含まれているので、NP困難な問題もありそうです。

解けていない問題の概要は以下のような感じです。形式的な定義は後述しますので、用語（方言）の意味が分からなくても大丈夫です。

  1. そのトポロジカルソートの"幅"の最小化（gitのコミットロググラフであまり横幅が広がらないようにしたい。あるいは、いつかやらないといけない仕事を覚えておく脳容量を減らせるスケジューリングがしたい）
  2. そのトポロジカルソートにおける最長の辺の長さの最小化（最適化コンパイラで命令の順番をどのようにすべきかに関連）
  3. そのトポロジカルソートにおける辺の長さの総和の最小化（関数型難解言語Grassのgolfをする時に解く必要のある問題）

　

  • 1.と3.の問題はbitDPを行うことで最適解を求めることできますが、グラフのサイズはそれなりに大きい（たとえばV~1000）ことを想定しているので現実的ではありません。
  • 2.の問題は、無向グラフの場合はbandwidth問題と呼ばれる問題（指数時間アルゴリズム入門の87ページ）で、Ο(5^|V|)時間アルゴリズムを構成したという論文が2012年に出たそうです（アイデアは2008年頃が初出？同著者からもっと底が小さいアルゴリズムも提案されている）。このアイデアは有向グラフでも適用できて、有向であるという制約のおかげで指数の底が小さくなりますが、2よりは大きそうです。

いろいろ調べてみたところ、無向グラフを扱っているものは計算量理論的な議論が多く、有向グラフを扱っているものはいかに見やすいDAGの可視化をするかというヒューリスティクス的アプローチの論文が多そうに感じました。

形式的定義

グラフとトポロジカルソートについて

頂点の集合をVとし、有向辺の集合をEとします。また、有向辺から有向辺の始点と終点の順序対への写像をfとします。 この三つ組G=(f,V,E)を有向グラフと呼びます。

このグラフに閉路が存在しないとき、それは有向非巡回グラフ (DAG) と呼ばれます。

その場合、二頂点間の到達可能性を二項関係とみなすと、これは半順序となります。

トポロジカルソートとは、その半順序関係を全順序に拡張したもののことを言います。

具体的には、Vの並べ替え（全単射） s:V→\{1, 2, 3, ..., |V| \}であって、次の条件を満たすもののこととします。

\forall v, w \ (vからwに到達可能) \rightarrow s(v) \le s(w)

一般にトポロジカルソートsは複数種類あり得ます。

参考

  • トポロジカルソートを何か一つ求める問題は、時間計算量Ο(|V|+|E|)で解くことができます。
  • トポロジカルソートが何通りあるかを調べる問題は#P完全です。いわゆるbitDPの典型問題として、Ο(|V|2^|V|)時間*1のアルゴリズムが存在します。

トポロジカルソートの"幅"の最小化

【問題】DAGであるGが与えられる。 \mathop{max}\limits_{i \in \{1, 2, 3, ..., |V|-1 \}} |\{ e | e \in E, g(v) \le i \land i \lt g(w) \ where \ (v,w) = f(e)\}|を最小化するトポロジカルソートsを求めよ。

無向グラフなら、（方言ではない）グラフの言葉を使うと、Cutwidthを最小化するLayoutを求めてください、という判定版がNP完全な問題になります。

bitDPで解ける、について

トポロジカルソートを前から順番に確定させていくとします。この時、すでに順番を確定させた頂点の集合をSと呼ぶことにします。

グラフを現在の位置で切った時の"幅"とはつまりSに含まれる頂点からSの補集合に含まれる頂点への辺の数であり、それはSのみによる情報です。そこにはSの中での並べ方の情報は一切含まれていません。

そこで、Sに含まれる頂点をうまく並べた時の最大"幅"は、「現在の位置で切った時の"幅"」と「Sから一つ頂点を除いた集合に含まれる頂点ををうまい順番で並べた時の最大幅」（Sから一つ頂点を除いた集合は一般に複数あります）を全て計算して、その最大値を取ることで計算できます。

この性質を利用すると、トポロジカルソートをΟ(|V|!)通り全探索するのではなく、Vの部分集合の包含関係に関する動的計画法（いわゆるbitDP）を行うことでΟ(|V|2^|V|)時間のアルゴリズムを構成できます（Sの部分集合が2^|V|通り、各SについてSから一つ頂点を取り除いた集合はΟ(|V|)通り）。

トポロジカルソートの最長の辺の長さの最小化

トポロジカルソートにおける辺の長さ は、 E→\mathbb{N}の関数lであって、 l(e) = s(w) - s(v) \ where \ (v, w) = f(e)で与えられるものとします（方言）。

【問題】DAGであるGが与えられる。 \mathop{max}\limits_{e \in E} l(e)を最小化するトポロジカルソートsを求めよ。

無向グラフなら、（方言ではない）グラフの言葉を使うと、Bandwidthを最小化するLayoutを求めてください、という判定版がNP完全な問題になります。

無向グラフ版を指数時間で解くアルゴリズム　M. Cygan, M. Pilipczuk (2012)

スカラー最適化問題を解くアルゴリズムを構成するうえで重要なテクニックに、「K以下の解があるかという決定問題を解くアルゴリズムを作る。するとKについて二分探索することで最適値を求めることができるようになる」というものがあります。この変換を行う利点は、「 K以下の解があると仮定する 。すると解をこのように構築できて…………あれ？うまくいかなかったから答えはNoです」みたいな動作をする、解の性質を用いた貪欲アルゴリズムが許されるようになる点です。普通、解の性質は解を求めるまで分かりませんから、それを使えるようになることはアルゴリズム的に有利に働くことがあります。

Bandwidth問題を解くアルゴリズムは、このテクニックを使っています。まず、最長の辺の長さをKだと仮定します。この時、トポロジカルソートの結果を格納する配列に、K+1要素ごとに仕切りを入れ、"部屋"に分けることを考えます。次に、頂点をどの"部屋"に入れるかであり得るパターンを全列挙することを考えます。何も制約がなければΟ( (|V|/K)^|V|)通りとなってしまって階乗通りと大差ありませんが、無向辺で結ばれている二つの頂点は、同じ"部屋"に入れるか二つある隣の”部屋”のどちらかに入れるかしかできません。よってパターン数はΟ(|V|/K 3^|V|)通りとなります（グラフが連結でなければ各連結成分の解を合わせれば解が求まるため、連結なグラフについての問題に帰着されます。よって連結だと仮定しても一般性を失いません。連結なら適当な全域木を考え、適当な頂点を根にとります。根は|V|/K個の部屋のどこにでも入れられます。他の頂点は全域木に含まれる無向辺の制約により3つの部屋のどれかにしか入れられません）。

部屋の割り当てが決まったからと言って、自動的に最長の辺の長さがK以下になるとは限りません。よって、頂点のその部屋内での位置を決める必要もあります。

部屋に入れるとき、インデックスの小さい方から入れていくことにします。頂点を入れていく順番はΟ(|V|!)通りありますが、実際には頂点を入れていった順番は何の情報も持っていなく、部屋に入れられた頂点の集合の区別のみが意味のある情報になっています（これは入れる順番と部屋の区切り方がうまいからです）。よって状態数はΟ(2^|V|)通りであり、特定の"部屋割り"について時間計算量Ο(|V|2^|V|)となります。

これを組み合わせれば、時間計算量Ο(|V|^2/K 6^|V|)のアルゴリズムが得られたことになります。

実際には最長の辺の長さがKを超えない状態はΟ(5^|V|)通りしかないため、bitDPではなくメモ化深さ優先探索を行うことでΟ*(5^|V|)時間で完了します。

なお、この方法は空間計算量がΟ*(2^|V|)ですが、同じ計算を何回も行うので少し無駄です。空間計算量が大きい代わりに時間計算量が小さいアルゴリズムがいくつか提案されています。

有向グラフ版を指数時間で解くアルゴリズムの案

同様の方法を使うと、部屋の割り当ては二通り（同じ部屋に入れるか次の部屋に入れるか）なのでΟ(|V|/K 2^|V|)通りになり、指数の底は4以下（3.5？）になります。

トポロジカルソートにおける辺の長さの総和の最小化

【問題】DAGであるGが与えられる。 \mathop{\sum}\limits_{e \in E} l(e)を最小化するトポロジカルソートsを求めよ。

無向グラフなら、（方言ではない）グラフの言葉を使うと、Minimum Linear Arrangement (MinLA) を最小化するLayoutを求めてください、という判定版がNP完全な問題になります。

bitDPで解ける、について

先ほどと同様にトポロジカルソートを前から順番に確定させていくとします。この時、すでに順番を確定させた頂点の集合をSと呼ぶことにします。

ここに一つ頂点を追加した時に増える辺の長さの計算には、やはりS内部の順番は無関係であることが重要な性質です（完全に自明というわけではありませんが、どのSに含まれる頂点からSの補集合に含まれる頂点への辺も区別する意味がないという性質があります）。

よってやはり先ほどと同様にbitDPを行うことができて、Ο(|V|2^|V|)時間のアルゴリズムを構成できます。

限定的な状況における解法

無向グラフ版の各種結果（参考文献1）

近似アルゴリズムについての結果

入力グラフに仮定を置いた場合の結果

  • MinLAは幾分簡単であり、木なら時間計算量Ο(|V|^(log3/log2))で、根付き木*2なら時間計算量Ο(|V|log|V|)で、それぞれ解けるアルゴリズムがあります。
  • Cutwidth問題は、最大次数3のグラフであっても判定版がNP完全となります。木なら時間計算量Ο(|V|log|V|)で解けるアルゴリズムがあります。
  • Bandwidth問題はさらに進んで二分木（最大次数3かつ木）であってすら判定版がNP完全となります。
    • 区間グラフの場合、時間計算量Ο(|V|+|E|)で解けるアルゴリズムがあります（対応する区間表現順に並べた場合が最適になります）。

固定パラメータ容易性 (Fixed Parameter Tractable, FPT)

  • Bandwidthが2のLayoutがあるか？という問題は時間計算量Ο(|V|)で解くことができます。
  • Cutwidthが2のLayoutがあるか？という問題は時間計算量Ο(|V|)で解くことができます。
  • 固定のkについて、Cutwidthがkのトポロジカルソートがあるか？という問題は時間計算量Ο(|V|^2)で解くことができます。kについてのオーダーがどのような恐ろしいものになっているかはわからないという点に注意してください。

有向グラフの場合、それとは対照的に、もしグラフの各頂点の入力辺が1本（つまり根付き木になっている）であれば、2-opt最適化を貪欲に繰り返していくことで解決できることが分かっています。

また、現実的な入力の多くでは、各頂点の入力辺が多くの場合1本、それほど少なくない割合で2本、という問題設定であり*3、入力辺が3本以上あることはないと仮定したアルゴリズムも実用上重要だと思われます。もっとも、最小有向閉路除去問題は入力辺を2本に限定しても判定版がNP完全だったはずなので、入力辺が2本という制約は本質的ではなくて、依然NP完全問題を帰着するのには十分な表現力があるのかもしれませんが……。

なお、この制約のもと、bitDPの時間計算量の多項式部分から|V|が消えますが、依然として2^|V|が立ちはだかります。

NP困難だった場合は適当な近似率保証のある近似アルゴリズムを見つけたいところです。

いずれの問題も、最悪のトポロジカルソートを持ってくると近似率がΘ(N)倍になってしまう例が簡単に作れます。

具体的には、2000頂点のグラフで、{ 1→2, 2→3, 3→4, ..., 999→1000 } ∪ { 1001→1002, 1002→1003, 1003→1004, ..., 1999→2000 } ∪ { 1→1001, 2→1002, 3→1003, ..., 1000→2000 }を辺に持つようなグラフを考えた時、1, 2, 3, 4, ..., 999, 1000, 1001, 1002, 1003, 1004, ..., 1999, 2000というトポロジカルソートは最悪であり、1, 1001, 2, 1002, 3, 1003, 4, 1004, ..., 999, 1999, 1000, 2000というトポロジカルソートは最良です。

参考文献

    1. Diaz, J.Petit, M. Serna, ACM Comput. Surv. 2002, 34, 313-356.

*1:トポロジカルソートは最大で|V|!個あるため、それを数えるには|V|log(|V|) bitの多倍長整数演算が必要になり、本当の計算量のオーダーはさらに|V|log(|V|)倍となります。ただし、適当な数で割った余りを求める問題として定式化する場合はこの問題はなくなります。あるいは、現実的な時間で解ける問題しか出題されないという制約、たとえば |V| \le 20であるとすれば64bitに収まるのでこの問題は隠されます。本文中の他の部分では、そこまで大きな整数の演算は必要ない（log(|V|) は64を超えない）という妥当な仮定のもと、log(|V|)項を無視した表記になっています。そもそも指数時間アルゴリズムなので非常に些細な違いであり、あまり気にする必要はありません。

*2:唐突に有向グラフが出てきたように思えますが、本当にあっているんでしょうか？

*3:gitのコミットグラフ、最適化コンパイラ、Grassのgolfという全く出自の違う問題群なのに、出来上がるDAGの特徴は似ている、というのはなかなか面白いことだと思います。