グラフ アルゴリズム の研究において、暗黙的グラフ表現(または単に暗黙的グラフ) とは、頂点またはエッジがコンピュータのメモリ内で明示的なオブジェクトとして表現されるのではなく、計算可能な関数などの他の入力からアルゴリズム的に決定されるグラフです。

暗黙のグラフの各頂点はボード上の正方形によって定義され、各エッジはナイトのツアーでの動きです。

近隣地域の表現

暗黙的グラフの概念は、グラフを用いて記述される様々な探索アルゴリズムで一般的である。この文脈において、暗黙的グラフは、任意の指定された頂点のすべての近傍を定義する規則の集合として定義することができる。[1]このタイプの暗黙的グラフ表現は、各頂点の近傍に簡単にアクセスできるという点で、隣接リストに類似している。例えば、ルービックキューブのようなパズルの解を探す場合、各頂点がキューブの可能な状態の一つを表し、各辺が一つの状態から別の状態への動きを表すような暗黙的グラフを定義することができる。パズルのすべての可能な動きを試し、それぞれの動きで到達する状態を決定することで、任意の頂点の近傍を生成するのは簡単である。しかし、ルービックキューブの状態空間は広すぎて、アルゴリズムでその状態をすべてリストすることはできないため、暗黙的表現が必要となる。[2]

計算複雑性理論では、頂点の近傍をリストするための規則またはアルゴリズムによって上記のように定義される暗黙的グラフに関連して、いくつかの複雑性クラスが定義されています。たとえば、 PPAは、入力として無向暗黙的グラフ (頂点はnビットのバイナリ文字列で、任意の頂点の近傍をリストするための多項式時間アルゴリズムを持つ) とグラフ内の奇数次数の頂点が与えられ、奇数次数の 2 番目の頂点を見つけなければならない問題のクラスです。ハンドシェイク補題により、そのような頂点は存在し、それを見つけることはNPの問題ですが、この方法で定義できる問題は、PPA = NP かどうか不明であるため、必ずしもNP 完全であるとは限りません。PPADは、暗黙的有向グラフ上で定義される類似のクラスで、ナッシュ均衡を計算する問題を含むため、アルゴリズムゲーム理論で注目を集めています。[3]暗黙的グラフ内のある頂点から別の頂点への到達可能性をテストする問題は、空間制限のある非決定性複雑性クラスを特徴付けるためにも使用できます。これには、 NL （頂点がO(log n )ビットのビット文字列である暗黙的有向グラフの到達可能性によって特徴付けられる問題のクラス）、 SL（無向グラフの類似クラス）、およびPSPACE（多項式長のビット文字列を持つ暗黙的グラフの到達可能性によって特徴付けられる問題のクラス）が含まれます。この複雑性理論のコンテキストでは、暗黙的グラフの頂点は非決定性チューリングマシンの状態を表し、エッジは可能な状態遷移を表しますが、暗黙的グラフは他の多くのタイプの組み合わせ構造を表すためにも使用できます。[4]別の複雑性クラスであるPLS は、暗黙的グラフで局所最適値を見つける複雑さを捉えます。[5]

暗黙的グラフモデルは、相対化されていないモデルにおける既知の分離よりも強い複雑性クラス間の分離を証明するための相対化の一形態としても用いられてきた。例えば、Childsらは暗黙的グラフの近傍表現を用いて、量子コンピュータでは多項式時間で解けるが、古典コンピュータでは指数時間を要するグラフ走査問題を定義した。[6]

隣接ラベル付けスキーム

グラフの効率的な表現の文脈において、JH Muller は、与えられたグラフ族F内のグラフGの局所構造または隣接ラベリングスキームを、 O (log n )ビットの識別子をGの各頂点に割り当てることと、 2つの頂点識別子を入力として受け取り、それらが G の辺の終点であるかどうかを判定するアルゴリズム（ Fに依存するが、個々のグラフGからは独立している）であると定義しました。つまり、このタイプの暗黙的な表現は隣接行列に似ています。2つの頂点が隣接しているかどうかを確認するのは簡単ですが、任意の頂点の隣接頂点を見つけるには、すべての頂点をループしてどの頂点が隣接しているかをテストする必要がある場合があります。[7]

隣接ラベル付けスキームを持つグラフ ファミリには次のものがあります。

有界次数グラフ
Gの各頂点が最大d 個の隣接頂点を持つ場合、 Gの頂点に1 からnまでの番号を振り、各頂点の識別子を、自身の番号と隣接頂点の番号の( d + 1)組とします。2 つの頂点は、一方の識別子の最初の番号がもう一方の識別子の後に現れるとき、隣接しています。より一般的には、同じアプローチを用いて、平面グラフや任意のマイナー閉グラフ族のグラフを含む、有界樹状性または有界退化を持つグラフの暗黙的な表現を提供することができます。[8] [9]
交差グラフ
区間グラフは、実数直線上の線分集合の交差グラフである。このグラフには、線分の端点に1から2 nまでの番号が付けられ、グラフの各頂点は対応する区間の2つの端点の番号で表される隣接ラベル付け方式が与えられる。この表現を用いると、2つの頂点を表す番号を比較し、それらの番号が重なり合う区間を定義していることを確認することで、それらの頂点が隣接しているかどうかをチェックすることができる。同じアプローチは、境界付き箱型グラフや円グラフ、そして距離遺伝グラフやコグラフといったこれらのファミリーのサブファミリーを含む他の幾何学的交差グラフにも適用できる。[8] [10]しかし、幾何学的交差グラフの表現は、必ずしも隣接ラベル付け方式の存在を意味するわけではない。なぜなら、各幾何学的オブジェクトを指定するために対数以上のビット数が必要になる場合があるからである。例えば、グラフを単位円グラフとして表現する場合、円の中心の座標に指数関数的に多くのビットが必要になる場合がある。[11]
低次元比較グラフ
半順序集合の比較可能性グラフは、各集合要素に対応する頂点と、半順序によって関連付けられた2つの集合要素間の辺を持つ。半順序の順序次元は、与えられた半順序が交点となる線形順序の最小数である。半順序が有界順序次元を持つ場合、その比較可能性グラフの頂点の隣接ラベル付けスキームは、各頂点に定義線形順序のそれぞれにおける位置をラベル付けし、対応する2つの頂点のラベル内の数値のペアが互いに同じ順序関係にある場合に、それらの頂点が隣接していると判断することによって定義できる。特に、これにより、最大4次元の半順序から得られる弦比較可能性グラフの隣接ラベル付けスキームが可能になる。 [12] [13]

暗黙のグラフ予想

全てのグラフ族が局所構造を持っているわけではない。いくつかの族については、単純な計数議論から隣接ラベリング方式が存在しないことが証明される。すなわち、グラフ全体を表すのにO ( n log n )ビットしか使用できないため、このタイプの表現は、与えられた族F内のn頂点グラフの数が最大で2 O ( n log n )である場合にのみ存在できる。二部グラフや三角形のないグラフなど、これよりも多くのグラフを持つグラフ族には、隣接ラベリング方式がない。[8] [10]ただし、族内のグラフの数が少ないグラフ族でも、隣接ラベリング方式がない可能性がある。たとえば、頂点よりも辺の数が少ないグラフ族には2 O ( n log n ) n頂点のグラフがあるが、隣接ラベリング方式はない。これは、この族内では、各辺に新しい孤立した頂点を追加することで、任意のグラフをより大きなグラフに変換でき、そのラベル付け可能性は変わらないためである。[7] [10] Kannanらは、禁制部分グラフの特性を持ち、かつ最大で 2 O ( nlogn ) n頂点グラフを持つことが、隣接ラベル付けスキームの存在を保証するのに十分かどうかを問うた。この問題は、Spinradが予想として再述した。最近の研究では、禁制部分グラフの特性を持ち、成長率が十分に遅いが、隣接ラベル付けスキームを持たないグラフの族を提供することで、この予想を反駁した。[14] この予想の条件を満たし、かつ隣接ラベル付けスキームが知られていないグラフの族には、ディスクグラフと線分交差グラフの族がある。

ラベリングスキームと誘導ユニバーサルグラフ

グラフ族Fが隣接ラベリング方式を持っている場合、F内のn頂点グラフは、すべての可能な頂点識別子からなるグラフである、多項式サイズの共通誘導ユニバーサルグラフの誘導サブグラフとして表現できます。逆に、このタイプの誘導ユニバーサルグラフが構築できる場合、その頂点の ID は、隣接ラベリング方式のラベルとして使用できます。[8]この暗黙のグラフ表現のアプリケーションでは、ラベルのビット数が誘導ユニバーサルグラフの頂点数に直接変換されるため、ラベルが使用するビット数をできるだけ少なくすることが重要です。 Alstrup と Rauhe は、任意のツリーがラベルあたりlog 2 n + O ( log * n )ビットの隣接ラベリング方式を持っていることを示し、このことから、樹木度kを持つ任意のグラフは、ラベルあたりk log 2 n + O ( log * n )ビットの方式とn k 2 O ( log * n )頂点を持つユニバーサルグラフを持つことになります。特に、平面グラフは樹木性が最大で 3 であるため、頂点数がほぼ立方数のユニバーサルグラフになります。[15] この境界は Gavoille と Labourel によって改良され、平面グラフとマイナー閉グラフ族はラベルあたり2 log 2 n + O (log log n )ビットのラベリングスキームを持ち、木幅 が制限されたグラフはラベルあたりlog 2 n + O (log log n )ビットのラベリングスキームを持つことが示されました。[16] 平面グラフの境界は、Bonamy、Gavoille、および Piliczuk によってさらに改良され、平面グラフはラベルあたり(4/3+o(1))log 2 nビットのラベリングスキームを持つことが示されました 。[17]最後に Dujmović らは、平面グラフはラベルあたり(1+o(1))log 2 nビット のラベリングスキームを持ち、n 1+o(1) 頂点を持つユニバーサルグラフになることを示しました。[18]

回避性

Aanderaa -Karp-Rosenberg予想は、任意の2つの頂点が隣接しているかどうかを判定するためのブラックボックスルールを持つ、ラベル付き頂点の集合として与えられた暗黙グラフに関するものです。この定義は、隣接ラベル付けスキームとは異なり、ルールはファミリー内のすべてのグラフに適用される一般的なルールではなく、特定のグラフに固有のルールである場合があります。この違いにより、すべてのグラフには暗黙的な表現があります。例えば、ルールは別の隣接行列で頂点のペアを検索するというものかもしれません。しかし、このタイプの暗黙グラフを入力として与えられたアルゴリズムは、テストの実装方法に関係なく、暗黙的な隣接テストのみを介してグラフを処理しなければなりません。

グラフプロパティとは、グラフが特定のグラフファミリーに属するかどうかという問題であり、その答えは頂点のラベルを変更しても不変でなければなりません。この文脈で決定されるべき問題は、特定の暗黙のグラフに対して関心のあるプロパティが真か偽かを判定する前に、最悪の場合、何組の頂点の隣接性を検査しなければならないか、ということです。Rivest と Vuillemin は、任意の非自明なグラフプロパティに対する決定論的アルゴリズムは、頂点の平方数のペアを検査しなければならないことを証明しました。[19]完全な Aanderaa–Karp–Rosenberg 予想は、単調なグラフプロパティ (そのプロパティを持つグラフにさらにエッジを追加しても真のままになるもの) に対する決定論的アルゴリズムは、場合によってはすべての可能な頂点のペアを検査しなければならないというものです。この予想はいくつかのケースで成立することが証明されている。例えば、頂点数が素数のグラフでは成立することが知られている[20]。しかし、完全な予想は未だに未解決である。この問題のランダム化アルゴリズムや量子アルゴリズムの変種も研究されている。

ベンダーとロンは、回避性予想に用いられたのと同じモデルにおいて、有向非巡回グラフと非巡回性からかけ離れたグラフを区別するのに定数時間しかかからないことを示した。対照的に、近傍ベースの暗黙的グラフモデルでは、これほど高速な処理は不可能である。[21]

参照

参考文献

  1. ^ Korf, Richard E. (2008)、「線形時間ディスクベース暗黙グラフ検索」、Journal of the ACM、55 (6) 26: 1– 40、doi :10.1145/1455248.1455250、MR  2477486、S2CID  13969607。
  2. ^ Korf, Richard E. (2008)、「2 ビット幅優先探索におけるディスク I/O の最小化」(PDF)、Proc. 23rd AAAI Conf. on Artificial Intelligence、pp.  317– 324、標準の 3×3×3 ルービック キューブには 4.3252 × 10 19 の状態が含まれており、網羅的に探索するには大きすぎます。
  3. ^ Papadimitriou, Christos (1994), 「パリティ論証の複雑さとその他の非効率的な存在証明について」(PDF)、Journal of Computer and System Sciences、48 (3): 498– 532、doi :10.1016/S0022-0000(05)80063-7、 2016年3月4日にオリジナル(PDF)からアーカイブ、 2011年7月12日取得
  4. ^ イマーマン、ニール(1999)、「演習 3.7 (すべてがグラフ)」、記述的複雑性、コンピュータサイエンス大学院テキスト、シュプリンガー・フェアラーク、p. 48、ISBN 978-0-387-98600-5。
  5. ^ Yannakakis, Mihalis (2009)、「平衡、不動点、複雑性クラス」、Computer Science Review、3 (2): 71– 85、arXiv : 0802.2831、doi :10.1016/j.cosrev.2009.03.004。
  6. ^ Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003)、「量子ウォークによる指数関数的アルゴリズムの高速化」、第35回ACMコンピューティング理論シンポジウム論文集、ニューヨーク：ACM、pp.  59– 68、arXiv：quant-ph/0209131、doi：10.1145/780542.780552、ISBN 1-58113-674-9、MR  2121062、S2CID  308884。
  7. ^ ab Muller, John Harold (1988)、「グラフクラスの局所構造」、ジョージア工科大学博士論文。
  8. ^ abcd Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992)、「グラフの暗黙的表現」、SIAM Journal on Discrete Mathematics、5 (4): 596– 603、doi :10.1137/0405049、MR  1186827。
  9. ^ Chrobak, Marek; Eppstein, David (1991)、「低出次数平面配向と隣接行列の圧縮」(PDF)、理論計算機科学、86 (2): 243– 266、doi : 10.1016/0304-3975(91)90020-3。
  10. ^ abc Spinrad, Jeremy P. (2003)、「2. 暗黙的グラフ表現」、効率的なグラフ表現、アメリカ数学会、pp.  17– 30、ISBN 0-8218-2815-0。
  11. ^ Kang, Ross J.; Müller, Tobias (2011), Sphere and dot product representations of graphs (PDF) , archived from the original (PDF) on 2012-03-16 , retrieved 2011-07-12。
  12. ^ Ma, Tze Heng; Spinrad, Jeremy P. (1991)、「Cycle-free partial orders and chordal comparability graphs」、Order、8 (1): 49– 61、doi :10.1007/BF00385814、MR  1129614、S2CID  120479154。
  13. ^ Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010)「線形時間における弦比較グラフの暗黙的表現」、Discrete Applied Mathematics、158 (8): 869– 875、doi : 10.1016/j.dam.2010.01.005、MR  2602811。
  14. ^ ハタミ、ハメド; Hatami、Pooya (2022)、「The implicit chart conjecture is false」、第 63 回 IEEE Annual Symposium on Foundations of Computer Science、FOCS 2022、デンバー、コロラド州、米国、2022 年 10 月 31 日 – 11 月 3 日、IEEE、pp.  1134 – 1137、arXiv : 2111.13198、doi :10.1109/FOCS54457.2022.00109
  15. ^ Alstrup, Stephen; Rauhe, Theis (2002)、「Small induced-universal graphs and compact implicit graph representations」（PDF） , Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science , pp.  53– 62, doi :10.1109/SFCS.2002.1181882, ISBN 0-7695-1822-2, S2CID 1820524, 2011年9月27日に オリジナル（PDF）からアーカイブ、 2011年7月13日取得。
  16. ^ Arnaud, Labourel; Gavoille, Cyril (2007)、「平面グラフと木幅制限付きグラフのより短い暗黙的表現」（PDF）、第15回ヨーロッパアルゴリズムシンポジウムの議事録、コンピュータサイエンスの講義ノート、第4698巻、pp.  582– 593、doi :10.1007/978-3-540-75520-3_52、ISBN 978-3-540-75519-7。
  17. ^ Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020)、「平面グラフの短縮ラベル付けスキーム」、2020 ACM-SIAM 離散アルゴリズムシンポジウム論文集、pp.  446– 462、arXiv : 1908.03341、doi :10.1007/978-3-540-75520-3_52。
  18. ^ ドゥイモヴィッチ、ヴィダ;ルイス、エスペレット。ジョレット、グエナエル。ガヴォイユ、シリル。ミチェク、ピョートル。モーリン、パット (2020)、「平面グラフの隣接ラベル付け (およびその先)」、第 61 回 IEEE 年次シンポジウム、コンピューター サイエンスの基礎、pp.  577–588、arXiv : 2003.04280、doi :10.1007/978-3-540-75520-3_52。
  19. ^ Rivest, Ronald L. ; Vuillemin, Jean (1975)、「A generalization and prove of the Aanderaa-Rosenberg conjecture」、Proc. 7th ACM Symposium on Theory of Computing、アルバカーキ、ニューメキシコ州、アメリカ合衆国、pp.  6– 11、CiteSeerX 10.1.1.309.7236、doi :10.1145/800116.803747、S2CID  16220596 {{citation}}: CS1 メンテナンス: 場所の発行元が見つかりません (リンク)。
  20. ^ カーン、ジェフ、サックス、マイケル、スターテヴァント、ディーン（1983年）、「回避性への位相的アプローチ」、コンピュータサイエンスの基礎に関するシンポジウム、ロサンゼルスアラミトス、カリフォルニア州、米国：IEEEコンピュータ協会、pp.  31– 33、doi：10.1109/SFCS.1983.4、ISBN 0-8186-0508-1。
  21. ^ Bender, Michael A.; Ron, Dana (2000)、「有向グラフの非巡回性のサブ線形時間でのテスト」、Automata, languages and programming (ジュネーブ, 2000)、Lecture Notes in Comput. Sci., vol. 1853, ベルリン: Springer, pp.  809– 820, doi :10.1007/3-540-45022-X_68, ISBN 978-3-540-67715-4、MR  1795937。