推移的還元

数学のグラフ理論の分野において、有向グラフDの推移的簡約とは、頂点v、wのすべてのペアに対して、 Dのvからwへの(有向)パスが存在するのは、そのようなパスが簡約内に存在する場合のみであるような、頂点が同じで辺が可能な限り少ない別の有向グラフです。推移的簡約は、Aho、Garey、Ullman (1972) によって導入され、その構築にかかる計算の複雑さに厳しい制限が設けられました。

より技術的には、削減はDと同じ到達可能性関係を持つ有向グラフです。同様に、Dとその推移削減は互いに同じ推移閉包を持つ必要があり、 Dの推移削減は、その特性を持つすべてのグラフ間で可能な限り少ないエッジを持つ必要があります。

有限有向非巡回グラフ（有向サイクルのない有向グラフ）の推移的簡約は一意であり、与えられたグラフのサブグラフです。ただし、（有向）サイクルのあるグラフでは一意性が保証されず、無限グラフでは存在すら保証されません。

これに密接に関連する概念である最小同値グラフは、同じ到達可能性関係を持ち、可能な限り少ない辺を持つDのサブグラフである。 ^[1] 違いは、推移的縮小はDのサブグラフである必要がないことである。有限有向非巡回グラフの場合、最小同値グラフは推移的縮小と同じである。しかし、サイクルを含む可能性のあるグラフの場合、最小同値グラフの構築はNP困難であるのに対し、推移的縮小は多項式時間で構築できる。

推移的簡約は、関係のペアを有向グラフ内の弧として解釈することによって、 集合上の抽象的な二項関係に対して定義できます。

有限有向グラフ Gの推移的簡約は、元のグラフと同じ到達可能性関係を持つ、可能な限り少ない辺を持つグラフです。つまり、グラフGに頂点xから頂点yへのパスがある場合、 Gの推移的簡約にもxからyへのパスが存在する必要があり、その逆も同様です。具体的には、 x から y へのパスと y から z へのパスがある場合、 y を含まない x から z へのパスは存在しない可能性があります。 x、y、および z の推移性とは、 x < y かつ y < z の場合、 x < z であることを意味します。 y から z への任意のパスに対して x から y へのパスがある場合、 x から z へのパスが存在します。ただし、 x から y および x から z への任意のパスに対して y から z へのパスが存在するということは真ではなく、したがって頂点 x と z 間の辺は推移的ではないウォークを表すため、推移的簡約では除外されます。次の画像は、非推移的な二項関係 (左) とその推移的縮小 (右) に対応するグラフの図を示しています。

有限有向非巡回グラフ Gの推移的縮約は一意であり、 Gの辺のうち、その端点間の唯一のパスとなるものから構成されます。特に、これは常に、指定されたグラフの全域サブグラフです。このため、この場合、推移的縮約は最小の同等のグラフと一致します。

二項関係の数学的理論では、集合X上の任意の関係Rは、集合X を頂点集合とし、R内で関係するすべての順序付き要素ペアに対して弧xyを持つ有向グラフとして考えることができる。特に、この方法により、半順序集合を有向非巡回グラフとして再解釈することができ、半順序の要素ペア間に順序関係x  <  yがある場合は常にグラフに弧xyが存在する。このように構築された有向非巡回グラフに推移的簡約操作を適用すると、半順序の被覆関係が生成され、ハッセ図によって視覚的に表現されることが多い。

推移的還元は、有向非巡回グラフ（引用グラフや引用ネットワークなど）として表現できるネットワークに対して使用され、ネットワーク間の構造的差異を明らかにしてきた。^[2]

サイクルを持つ有限グラフでは、推移的縮約は一意ではない可能性がある。つまり、与えられたグラフと同じ到達可能性関係を持ち、最小の辺数を持つグラフが、同じ頂点集合上に複数存在する可能性がある。さらに、これらの最小グラフのいずれもが与えられたグラフのサブグラフではない可能性がある。それでも、与えられたグラフGと同じ到達可能性関係を持つ最小グラフを特徴付けることは簡単である。^[3] G が任意の有向グラフであり、HがGと同じ到達可能性関係を持つ辺の数が最小のグラフである場合、H は以下で構成される。

• Gの強連結成分ごとに、この成分内の頂点を連結する有向閉路
• Gの凝縮の推移的縮小の各辺XYに対する辺xy 。ここで、XとY は凝縮内の辺で接続されたGの 2 つの強く接続されたコンポーネント、 xはコンポーネントXの任意の頂点、y はコンポーネントYの任意の頂点です。 Gの凝縮は、 Gの強く接続されたコンポーネントごとに頂点があり、 G内の辺で接続された 2 つのコンポーネントごとに辺がある有向非巡回グラフです。特に、非巡回であるため、その推移的縮小は前のセクションのように定義できます。

このタイプの推移的縮小におけるエッジの総数は、凝縮の推移的縮小におけるエッジの数と、非自明な強連結成分 (複数の頂点を持つ成分) の頂点の数の合計に等しくなります。

凝縮辺に対応する推移的縮小の辺は、常に与えられたグラフGのサブグラフとして選択できる。しかし、各強連結成分内のサイクルは、その成分がハミルトン閉路を持つ場合にのみGのサブグラフとして選択できるが、これは常に真であるとは限らず、確認も難しい。この困難さのため、与えられたグラフGの同じ到達可能性を持つ最小のサブグラフ（その最小の同等のグラフ）を見つけることはNP困難である。^[3]

Aho らは、無限グラフではグラフが非巡回であっても推移的縮小が存在しない可能性があることを示すために次の例を挙げています。 が実数であるときはいつでも、各実数に対して頂点を持ち、辺を持つグラフを形成します。すると、このグラフは無限、非巡回、推移的に閉じています。ただし、同じ推移閉包を持つサブグラフでは、残りの各辺は推移閉包を変更することなく削除できます。これは、から へのパスがそれらの間の任意の頂点を通過する必要があるためです。したがって、同じ推移閉包を持つサブグラフのうち、これらのサブグラフはいずれも極小ではありません。つまり、推移的縮小は存在しません。^[3]${\displaystyle x\to y}$${\displaystyle x<y}$${\displaystyle x\to y}$${\displaystyle x}$${\displaystyle y}$

Aho らが示しているように、^{[3]グラフ アルゴリズムの}時間計算量がグラフの頂点の数nの関数としてのみ測定され、辺の数の関数としては測定されない場合、有向非巡回グラフの推移閉包と推移簡約は同じ計算量になります。推移閉包とサイズn  ×  nのブール行列の乗算は計算量が同じであることはすでに示されていたため、^[4]この結果により推移簡約は同じクラスに分類されます。2023年現在、行列乗算の最良厳密アルゴリズムはO( n ^2.371552 ) の時間がかかり、^[5]整数上の行列に適用して結果の非ゼロのエントリを調べることで、密なグラフの推移簡約の最悪ケースの時間境界が得られます。

推移的還元が推移的閉包と同じくらい簡単であることを証明するために、Aho らはブール行列乗算との既知の同等性に頼っています。彼らは、 Aを与えられた有向非巡回グラフの隣接行列とし、B をその推移的閉包の隣接行列とします（任意の標準的な推移的閉包アルゴリズムを使用して計算されます）。すると、辺uv が推移的還元に属するのは、行列Aの行uと列vに非ゼロのエントリがあり、行列積ABの同じ位置にゼロのエントリがある場合のみです。この構成では、行列ABの非ゼロ要素は、長さが 2 以上であるパスで接続された頂点のペアを表します。^[3]

推移的縮約が推移的閉包と同じくらい難しいことを証明するために、Aho らは与えられた有向非巡回グラフGから別のグラフH を構築した。このグラフでは、 Gの各頂点が3 つの頂点のパスによって置き換えられ、Gの各辺はH内のこれらのパスの対応する中間の頂点を結ぶ辺に対応する。さらに、グラフHにおいて、Aho らはすべてのパスの始点からすべてのパスの終点への辺を追加した。Hの推移的縮約では、辺uv がGの推移的閉包に属さない場合に限り、uのパスの始点からvのパスの終点への辺が存在する。したがって、Hの推移的縮約が効率的に計算できれば、Gの推移的閉包はそこから直接読み取ることができる。^[3]

有向非巡回グラフの頂点の数nと辺の数mの両方で測定すると、推移的縮小も O( nm ) の時間で見つけることができ、この制限はスパース グラフの行列乗算法よりも高速である可能性があります。これを行うには、開始頂点の可能な選択肢ごとに、指定された有向非巡回グラフで線形時間の 最長経路アルゴリズムを適用します。計算された最長経路から、長さが 1 (単一の辺) のものだけを保持します。言い換えると、uからvへの他の経路が存在しない辺 ( u、v ) を保持します。この O( nm ) の時間制限は、深さ優先探索または幅優先探索を使用して開始頂点のすべての選択肢から到達可能な頂点を見つけることによって推移閉包を構築する複雑さと一致するため、これらの仮定を繰り返すと、推移的閉包と推移的縮小は同じ時間で見つけることができます。

推移的縮約においてn頂点、m辺、r辺を持つグラフの場合、出力に敏感なアルゴリズムを使用して推移的縮約をmの代わりにrに依存する時間で見つけることが可能である。アルゴリズムは以下の通りである: ^[6]

• 各頂点vについて、入力グラフの 位相順序の逆順で次のようになります。
  • vから到達可能な頂点の集合を初期化します。最初はシングルトン集合 { v } です。
  • 各辺vwについて、 wによる位相的な順序で、wがvの到達可能な集合内にあるかどうかをテストし、そうでない場合は次の操作を実行します。
    • 推移的削減の一部としてエッジvwを出力します。
    • vから到達可能な頂点の集合を、その和集合によってwの到達可能な集合に置き換えます。

内側のループ内のエッジの順序は、カウンティングソートまたは他の安定したソートアルゴリズムを2回使用して、エッジをソートすることで取得できます。最初は終了頂点の位相番号で、次に開始頂点でソートします。セットがビット配列として表現されている場合、各セットの結合操作はO ( n )の時間で実行できます。または、ビット演算を使用するとより高速になります。これらのセット操作の数は出力エッジの数に比例するため、全体の時間制限はO ( nr )になります。アルゴリズムの実行中に取得される到達可能セットは、入力の推移閉包を表します。^[6]

グラフが頂点をk個のチェーン（ペアワイズ到達可能部分集合）に分割して与えられている場合、各到達可能集合をチェーンの接尾辞の和集合として簡潔に表現することで、この時間をさらにO（kr）に短縮することができます。^[7]

• Aho, AV ; Garey, MR ; Ullman, JD (1972)、「有向グラフの推移的縮約」、SIAM Journal on Computing、1 (2): 131–137、doi :10.1137/0201008、MR  0306032。
• Clough, JR; Gollings, J.; Loach, TV; Evans, TS (2015)、「引用ネットワークの推移的縮減」、Journal of Complex Networks、3 (2): 189–203、arXiv : 1310.8224、doi :10.1093/comnet/cnu039。
• ファーマン、ME (1970)、「グラフの推移閉包を求める問題への行列の高速乗算法の応用」、Doklady Akademii Nauk SSSR (ロシア語)、194 : 524、MR  0270950
• Goralčíková, Alla; Koubek, Václav (1979)、「グラフの縮約および閉包アルゴリズム」、Becvár, Jirí (編)、Mathematical Foundations of Computer Science 1979、議事録、第 8 回シンポジウム、オロモウツ、チェコスロバキア、1979 年 9 月 3 ～ 7 日、Lecture Notes in Computer Science、vol. 74、Springer、pp. 301 ～ 307、doi :10.1007/3-540-09526-8_27、ISBN 978-3-540-09526-2。
• モイルズ、デニス M.;トンプソン、ジェラルド L. (1969)、「有向グラフの最小等価グラフを見つけるためのアルゴリズム」、Journal of the ACM、16 (3): 455–460、doi : 10.1145/321526.321534。
• サイモン、クラウス (1988)、「非巡回有向グラフ上の推移閉包の改良アルゴリズム」、理論計算機科学、58 (1–3): 325–346、doi :10.1016/0304-3975(88)90032-1、MR  0963268。
• ウィリアムズ、バージニア・ヴァシレフスカ、徐、銀占、徐、子舒、周、人飛 (2023)、行列乗算の新しい境界：アルファからオメガへ、arXiv：2307.07970。

• ワイスシュタイン、エリック W.、「推移的還元」、MathWorld