群ラベル制約付き最短路問題 -

この記事は「データ構造とアルゴリズム Advent Calendar 2019」 $4$ 日目の記事です．*1
$3$ 日目は @921603 さんによる「Proximity search：列挙アルゴリズムの新たな構築手法」です．
$5$ 日目は @TsuMakoto さんによる「IDA* with Pattern Databaseでパズルを解く」です．

グラフにおける最短路問題は組合せ最適化の古典的な問題ですよね．今回は，その制約付きの変種に対する効率的なアルゴリズムを紹介したいと思います．元ネタは，来年 $1$ 月に開催される SODA という離散アルゴリズムの国際会議に採択されている以下の論文です．

Yutaro Yamaguchi: A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 1923‒1932. (Link) *2

奇しくも著者の方とイニシャルが同じ (Y.Y.) でした．運命的ですね．

昨日は STOC だったし，最新の SODA と言うと「難しいんじゃ…？」と思う方も居るかもしれませんが，

- It gives a very simple algorithm for an important problem, ...

- The algorithm is simple enough to teach to undergraduates (without the proof of correctness, at least).

- The idea of the algorithm is simple to explain, ...

などと評価されていたため，きっと大丈夫かと思います．*3 これなら競技プログラミングの問題としても出題できそうですね！

では早速中身に入っていきましょう．以下では，入力グラフの頂点数を $n$ ，枝数を $m$ で表すことにします．また，パスと言ったときには，単純経路を指すものとし，同じ頂点を複数回通るようなものは許さないことに注意してください．

無向グラフにおける最短路問題（制約無し）

古典的な問題とはいえ，導入として普通の最短路問題から始めましょう．

入力 $G = (V, E)$ : 無向グラフ， $\ell \colon E \to \mathbf{R}_{\ge 0}$ : 枝長， $s, t \in V$ : 端点対
目標 $\ell$ に関して最短である $G$ 中の $s$ – $t$ パス $P$ の発見

f:id:ygussany:20191202184940p:plain — 図1: 最短路問題のインスタンスと最適解の例

f:id:ygussany:20191202185102p:plain — 図1: 最短路問題のインスタンスと最適解の例

この問題は，Dijkstra 法*4などを用いれば，効率的に*5解くことができます．

定理 (Dijkstra 1959) 最短路問題に対する決定性 $\mathrm{O}(n^2)$ 時間アルゴリズムが存在する．*6

このアルゴリズムは，始点 $s$ から到達可能な任意の点への $\ell$ に関する最短路を含むような， $G$ 中の木を計算できます．この木を， $s$ を根とする $(G, \ell)$ の最短路木と呼ぶことにします．

無向グラフにおける最短奇パス問題

効率的に解ける制約付き最短路問題として，以下の問題が知られています．

入力 $G = (V, E)$ : 無向グラフ， $\ell \colon E \to \mathbf{R}_{\ge 0}$ : 枝長， $s, t \in V$ : 端点対
目標 $\ell$ に関して最短である $G$ 中の奇数枝数 $s$ – $t$ パス $P$ の発見

f:id:ygussany:20191202191038p:plain — 図2: 最短奇パス問題での実行不能解 P' と最適解 P の例

f:id:ygussany:20191202191046p:plain — 図2: 最短奇パス問題での実行不能解 P' と最適解 P の例

先ほどとの違いは，見つけたい対象に「奇数本の枝を使っている」という制約条件が加わったことだけです．*7 この問題は，最小重み完全マッチング問題に帰着でき，効率的に解けることが知られています．さらに，直接的で高速なアルゴリズムが設計できることも知られています．

定理 (Derigs 1985)*8 最短奇パス問題に対する決定性 $\mathrm{O}(\min\{n^2, m\log n\})$ 時間アルゴリズムが存在する．

今回紹介するアルゴリズムは，この Derigs のアルゴリズムに触発され，それを拡張したような形になっています．

群ラベル付きグラフにおける最短非零パス問題

さて，では今回扱う問題を導入しましょう．群ラベル付きグラフとは，無向グラフの各枝に，固定された群の要素がラベルとして付いているようなものです．ラベル付けには向きの情報が付随していて，逆向きに通ると逆元がラベルとして読まれるものとします．

抽象的な定義より，例を見た方が早いので，さっさと進みましょう．定義では $\Gamma$ を任意の群としますが，馴染みが無ければ整数の加法群 $(\mathbf{Z}, +)$ などを考えてもらえばよいです．実際，以下では $\Gamma = (\mathbf{Z}, +)$ の場合を例に進めます．

入力 $G = (V, E)$ : $\Gamma$ ラベル付きグラフ， $\ell \colon E \to \mathbf{R}_{\ge 0}$ : 枝長， $s, t \in V$ : 端点対
目標 $\ell$ に関して最短である $G$ 中の非零ラベル $s$ – $t$ パス $P$ の発見

f:id:ygussany:20191202213440p:plain — 図3: 最短非零パス問題のインスタンスの例（黒がラベル，青が枝長）

f:id:ygussany:20191202211741p:plain — 図4: 最短非零パス問題での実行不能解 P' と最適解 P の例

f:id:ygussany:20191202211744p:plain — 図4: 最短非零パス問題での実行不能解 P' と最適解 P の例

例を見てもらえればイメージは掴めると思いますが，この問題での目標は，パスに沿って自然に定まるラベル $\psi_G(P)$ が非零である（群 $\Gamma$ の単位元でない）ような $s$ – $t$ パス $P$ の中で， $\ell$ に関して最短のものを求めることです．

この問題は，ラベル付けに用いる群 $\Gamma$ に依って様子が変わってきます．たとえば，位数 $2$ の群 $\mathbf{Z} / 2\mathbf{Z} = (\{0, 1\}, \oplus)$ を $\Gamma$ として選ぶと，先ほどの最短奇パス問題と本質的に等価な問題になります．また，曲面 $S$ に埋め込まれたグラフに対し， $S$ の基本群を $\Gamma$ として選び，適切に枝のラベルを設定することで，埋め込まれた曲面上で非可縮な閉路*9を求める問題などを定式化することもできます．

今回紹介するのは，群 $\Gamma$ に依らず*10，最短非零パス問題を効率的に解くアルゴリズムです．

定理 (Yamaguchi 2020) 最短非零パス問題に対する決定性 $\mathrm{O}(nm)$ 時間アルゴリズムが存在する．

アルゴリズム

いよいよ本題のアルゴリズムの紹介です．方針は十分にシンプルで，以下の通りです．ここでも，簡単のため， $\Gamma = (\mathbf{Z}, +)$ として話を進めますが，任意の群に取り替えても（非可換だろうが無限だろうが）正しく動くというのが紹介論文の強みです．

まず，制約を無視して Dijkstra 法で $s$ を根とする $(G, \ell)$ の最短路木 $T$ を求める．
$T$ に含まれる唯一の $s$ – $t$ パス $P_t$ のラベルが非零 $(\psi_G(P_t) \neq 0)$ であれば， $P_t$ を出力して終了する．
$\psi_G(P_t) = 0$ であれば， $P_t$ とラベルが違う $s$ – $t$ パスの中で $\ell$ に関して最短のもの $Q$ を求めて出力する．

f:id:ygussany:20191203085134p:plain — 図5: 最短路木 T とステップ 3 での目標（Q の発見）

1, 2 は Dijkstra 法を実行して，その出力をチェックするだけなので，簡単にできますね．問題は 3 で，この部分を正しく実行するアルゴリズムが以下の主題となります．ここで，以下の補題が重要となります．直観的には，良い非零ラベル閉路 $C$ が存在して， $C$ が欲しい解を即座に誘導するか，そうでなければ $C$ をある程度潰しても大丈夫である，ということを主張しています．

補題任意の最短路木 $T$ に対して，ある枝 $e \in E \setminus T$ が存在して， $T + e$ 中の唯一の閉路 $C$ が以下の性質をすべて満たす．ここで， $C$ 上で $s$ に最も近い点を $b$ とする．

$C$ は非零ラベルである． $(\psi_G(C) \neq 0)$
$C - b$ の任意の点 $w$ に関して， $C$ に関して $T$ を迂回して得られる $s$ – $w$ パス $Q_w$ は， $\psi_G(Q_w) \neq \psi_G(P_w)$ を満たす中で $\ell$ に関して最短の $s$ – $w$ パスである．
$C - b$ 以外の任意の点に関して， $C$ を $b$ に適切に縮約すれば，問題（ステップ 3 での目標）を本質的に保ったままインスタンスのサイズを小さくできる．

f:id:ygussany:20191203090836p:plain — 図6: 補題の気持ち

この補題により，現状のインスタンス（＋最短路木）に関して条件を満たす枝 $e$ を効率的に発見できさえすれば，

$C - b$ 中に $t$ が居れば， $C$ に関する迂回路（を元のグラフに展開したもの）を出力，
$C - b$ 外に $t$ が居れば， $C$ を $b$ に適切に縮約して再帰，

という単純な構造のアルゴリズムを作ることができます．各再帰では頂点数が必ず減るので，再帰の深さは高々 $n$ で，一度でも前者の状況になれば終わりなので，繰り返し回数自体が $n$ で押さえられますね．

「適切に縮約する」とは何なのか，ということを厳密に定義するのは，概念の簡単さに比べて不必要に面倒なので，直観的な説明と図だけに留めます．直観的には， $b$ から $C$ の周辺の各頂点への $C$ に沿った部分パスの情報（ラベルと長さ）だけを， $2$ 本の多重枝として残し，その他はすべて忘れてしまう，ということです．言い換えると， $C$ と変な交わり方をするような $s$ – $t$ パスは，今回の問題を解く上では考える必要が無いということです．図は気持ちで読み取ってください．

f:id:ygussany:20191203093906p:plain — 図7: 適切な縮約（C に沿った部分パスの情報だけを残す）

さて，最後に，補題の条件を満たす枝 $e$ を効率的に見つけられるかという問題を解決しましょう．これには簡単な判定方法があり，毎回 $\mathrm{O}(m)$ 時間で見つけられる，ということが以下の主張から従います．再帰の回数が高々 $n$ であったので，これにより，全体として $\mathrm{O}(nm)$ 時間のアルゴリズムが完成します．

主張任意の最短路木 $T$ に対して，非零ラベル閉路 $C$ を形成するような枝 $e = \{u, v\} \in E \setminus T$ のうち， $\frac{1}{2}\left(\ell(P_u) + \ell(P_v) + \ell(e)\right)$ を最小にするようなものを選べば，補題の条件を満たす．

論文中では， $T + e$ に含まれるような非零ラベル閉路 $C$ を blossom と呼び，主張中で定義されている値をその高さと定義し，最も低い blossom を探せば良い，と書かれています．

f:id:ygussany:20191203092507p:plain — 図8: 主張の気持ち（最も低い blossom を見つければよい）

まとめ

群ラベル付きグラフにおける最短非零パス問題に対して，ラベル付けに用いる群に依らない多項式時間アルゴリズムを紹介しました．アイデアとしては，

まず Dijkstra 法で最短路木 $T$ を求めて，
$T$ 中の $s$ – $t$ パス $P_t$ が非零ラベルならそれを出力して終わりで，
そうでなければ，

$T$ に関する良い非零ラベル閉路 $C$ (with $b$ ) を（最も低い blossom を）見つけて，
$C - b$ 上に目標点 $t$ があれば，迂回路（を元のグラフに展開したもの）を出力して終わりで，
そうでなければ $C$ を $b$ に縮約して再帰する，

という非常にシンプルな構造でした．計算時間も $\mathrm{O}(nm)$ となっていて，とても綺麗な結果でしたね．

*1:ブログとしてはちょうど一年ぶりの更新，わかりやすいですね．

*2:その後，改良版がリリースされているようです．すごいですね！
Yoichi Iwata, Yutaro Yamaguchi: Finding a Shortest Non-zero Path in Group-Labeled Graphs. arXiv:1906.04062. (Link)

*3:前提知識として，最短路問題に対する Dijkstra 法と，最大マッチング問題に対する Edmonds の花縮約アルゴリズムをなんとなく聞いたことがある，という程度を仮定します．

*4:E. W. Dijkstra: A note on two problems in connexion with graphs. Numerische Mathematik, 1 (1959), pp. 269–271. (DOI: 10.1007/BF01386390)

*5:枝長に関する計算（実数の四則演算や大小比較）は，基本演算として定数時間で実行できることを仮定します．

*6:このアルゴリズムは，優先度付きキューなどのデータ構造を用いて実装することで，より高速化できることも知られています．

*7:この問題は最短路問題（制約無し）を含んでいます．入力グラフで， $s$ 周りの枝以外全てをそれぞれ長さ半分の直列枝 $2$ 本で置き換えれば，任意の $s$ – $t$ パスの $\ell$ に関する長さを保ったまま，それら全てを実行可能解にできます．

*8:U. Derigs: An efficient Dijkstra-like labeling method for computing shortest odd/even paths. Information Processing Letters, 21 (1985), pp. 253–258. (DOI: 10.1016/0020-0190(85)90094-8)

*9:曲面として，トーラスやクラインの壺のようなものを想像してください．すると，その上の閉曲線で，どんな連続変形でも $1$ 点に潰せないようなものが取れるのがわかるかと思います．

*10:枝長に関する計算と同じく，ラベルに関する初等的な操作（群演算や要素の同一性判定，逆元の取得）は，基本演算として定数時間で実行できることを仮定します．