パス幅

パス分解は、連続するグラフの頂点のペアを識別して貼り合わせたグラフのシーケンスG _iとして記述でき、これらの貼り合わせをすべて実行した結果がGになります。グラフG _{i は}、パス分解の最初の定義における集合X _iの誘導部分グラフとみなすことができ、連続する誘導部分グラフの 2 つの頂点は、 Gの同じ頂点によって誘導される場合に貼り合わせられ、反対方向には、集合X _{i を}グラフG _iの頂点集合として復元できます。パス分解の幅は、グラフG _iのいずれかの最大頂点数より 1 つ少なくなります。^{[ 2 ]}

任意のグラフGのパス幅は、G を部分グラフとして含む区間グラフの最小クリーク数より 1 小さい値に等しい。 ^{[ 12 ]}つまり、Gの任意のパス分解に対して、 Gの区間スーパーグラフを見つけることができ、Gの任意の区間スーパーグラフに対して、分解の幅が区間グラフのクリーク数より 1 小さいGのパス分解を見つけることができる。

一方の方向について、 Gのパス分解が与えられているとします。このとき、分解のノードを（パスの順序で）直線上の点として表し、各頂点v をこれらの点を端点とする閉区間として表すことができます。このようにして、v を含むパス分解ノードは、 vの区間内の代表点に対応します。Gの頂点から形成される区間の交差グラフは、G を部分グラフとして含む区間グラフです。その最大クリークは、代表点を含む区間の集合によって与えられ、その最大クリークサイズは、1 にGのパス幅を加えた値になります。

反対に、G がクリーク数p + 1の区間グラフの部分グラフである場合、G は幅pのパス分解を持ち、そのノードは区間グラフの最大クリークによって与えられます。たとえば、図に区間表現で示されている区間グラフは、5 つの最大クリークABC、ACD、CDE、CDF、およびFGに対応する 5 つのノードを持つパス分解を持ちます。最大クリークサイズは 3 であり、このパス分解の幅は 2 です。

パス幅と区間厚のこの等価性は、与えられたグラフが部分グラフである弦グラフのツリー幅と最小クリーク数（マイナス1）の等価性と非常に類似しています。区間グラフは弦グラフの特殊なケースであり、弦グラフは、区間グラフがパスの部分パスの交差グラフであるという性質を一般化した、共通ツリーの部分ツリーの交差グラフとして表現できます。

Gの頂点の線形順序付けに関するGの頂点分離数は、各頂点vに対して、順序付けでvより前にある頂点のうち、 vまたはそれ以降の頂点を隣接点として持つ頂点が最大s個となるような最小の数sです。 Gの頂点分離数は、 Gの任意の線形順序付けに関するGの最小の頂点分離数です。頂点分離数はEllis、Sudborough 、 Turner (1983)によって定義され、 Gのパス幅に等しくなります。^{[ 13 ]} これは、以前の区間グラフのクリーク数との等価性から導かれます。Gが区間グラフIの部分グラフであり、すべての区間の端点が異なるように (図のように) 表現されている場合、Iの区間の左端点の順序付けの頂点分離数は、 Iのクリーク数より 1 小さいです。また、反対方向には、Gの線形順序付けから、ある頂点vの区間の左端点が順序付けにおけるその頂点の位置であり、右端点が順序付けにおいて最後に来るvの隣接頂点の位置であるような区間表現を導き出すことができる。

グラフ上のノード探索ゲームは、グラフ内に隠れている逃亡者を複数の探索者が協力して追跡する追跡回避ゲームの一種です。探索者はグラフの頂点に配置され、逃亡者はグラフの任意の辺上に存在できます。逃亡者の位置と動きは探索者には隠されています。各ターンで、探索者の一部または全員が（必ずしも辺に沿ってではなく、任意に）ある頂点から別の頂点へ移動し、その後、逃亡者は探索者が占有している頂点を通過しないグラフ内の任意の経路に沿って移動できます。逃亡者の辺の両端が探索者によって占有されたときに、逃亡者は捕まります。グラフのノード探索数は、逃亡者がどのように移動しても必ず捕まることを保証するために必要な最小の探索者数です。Kirousis & Papadimitriou (1985) が示すように、グラフのノード探索数はその区間の厚さに等しくなります。探索者にとって最適な戦略は、探索者を移動させて、連続するターンで最小の頂点分離数を持つ線形順序の分離集合を形成することである。

パス幅は固定パラメータ扱い可能であり、任意の定数kに対して、パス幅がk以下であるかどうかをテストし、そうであれば幅kのパス分解を線形時間で見つけることができる。^{[ 7 ]}一般に、これらのアルゴリズムは 2 つのフェーズで動作する。第 1 フェーズでは、グラフのパス幅がkであるという仮定を使用して、最適ではないが、幅がkの関数として制限できるパス分解または木分解を見つける。第 2 フェーズでは、最適な分解を見つけるために、この分解に動的計画法アルゴリズムが適用される。ただし、この種の既知のアルゴリズムの時間制限はk ²に対して指数関数的であり、 kの最小値を除いて実用的ではない。^{[ 33 ]} k = 2の場合、パス幅 2 のグラフの構造的分解に基づく明示的な線形時間アルゴリズムがde Fluiter (1997)によって与えられている。

ボドレンダー (1994) は、さまざまな特殊なグラフクラスにおけるパス幅の計算の複雑さを概説している。グラフGのパス幅がk以下であるかどうかを判定することは、 Gが有界次数グラフ^{[ 34 ]}平面グラフ^{[ 34 ]}有界次数平面グラフ^{[ 34 ]}弦グラフ[ ^{35 ]弦}ドミノ^{[ 36 ]}比較グラフの補グラフ[ ^{29 ]} および二部距離遺伝グラフ^{[ 37} ] に限定されている場合、NP 完全のままである。したがって^、二部グラフ、弦二部グラフ、距離遺伝グラフ、円グラフなど、二部距離遺伝グラフを含むグラフ族についても、NP 完全であることがすぐ^にわかる。^{[ 37 ]}

しかし、パス幅は木や森の場合は線形時間で計算できます。^{[ 9 ]}また、直列並列グラフ、外平面グラフ、ハリングラフなどの木幅が制限されたグラフ、^{[ 7 ]}分割グラフ、^{[ 38 ]}弦グラフの補グラフ、^{[ 39 ]}順列グラフ、^{[ 28} ]コグラフ、^{[ 27 ]}円弧グラフ、^{[ 40 ]}区間順序の比較グラフ、[30] およびもちろん区間グラフ自体についても、^パス幅はグラフの^区間表現で任意の点を覆う区間の最大数より 1 つ少ないだけなので、多項式時間で計算できます。

グラフのパス幅を加算定数の範囲内で近似することはNP困難である。^{[ 6 ]}パス幅の多項式時間近似アルゴリズムの 既知の最良の近似比はO ((log n ) ^3/2 )である。^{[ 41 ]} パス幅の以前の近似アルゴリズムについては、Bodlaender et al. (1992)およびGuha (2000)を参照。制限されたクラスのグラフの近似については、Kloks & Bodlaender (1992)を参照。

グラフの族Fがマイナーを取ることに関して閉じている場合 ( FのメンバーのすべてのマイナーがFにも含まれている場合)、 Robertson–Seymour の定理 により、Fは、禁止マイナーの有限集合Xにマイナーを持たないグラフとして特徴付けられます。^{[ 42 ]}例えば、Wagner の定理は、平面グラフは、完全グラフK ₅も完全二部グラフK _3,3もマイナーとして持たないグラフであると述べています。多くの場合、 Fの特性とXの特性は密接に関連しており、この種の最初の結果はRobertson & Seymour (1983)によるもので、^{[ 2 ]}有界パス幅と禁止マイナーの族における森の存在を関連付けています。具体的には、 Fのすべてのグラフのパス幅が最大でpであるような定数pが存在する場合、グラフの族Fは有界パス幅を持つと定義します。すると、マイナーが閉じた族F のパス幅が制限されるのは、 Fの禁止マイナーの集合Xに少なくとも 1 つのフォレストが含まれる場合に限る。

一方の方向では、この結果は簡単に証明できます。Xに少なくとも 1 つの森が含まれていない場合、Xマイナーフリー グラフのパス幅は制限されません。なぜなら、この場合、Xマイナーフリー グラフにはすべての森が含まれ、特に完全二分木が含まれるからです。しかし、 2 k + 1レベルの完全二分木のパス幅はkなので、この場合、Xマイナーフリー グラフのパス幅は無制限になります。もう一方の方向では、Xにn頂点の森が含まれている場合、Xマイナーフリー グラフのパス幅は最大でn − 2になります。^{[ 43 ]}

パス幅が最大pであるという性質は、それ自体がマイナーの取り方に関して閉じている。Gの幅が最大pのパス分解を持つ場合、 Gから任意のエッジが削除されても同じパス分解は有効であり、 Gおよびそのパス分解から任意の頂点を削除しても幅は増加しない。エッジの縮約も、縮約されたエッジの 2 つの端点を表すサブパスをマージすることで、分解の幅を増やすことなく実行できる。したがって、パス幅が最大pのグラフは、除外されたマイナーの集合X _pによって特徴付けられる。^{[ 42 ] [ 44 ]}

X _{p に}は必ず少なくとも 1 つの森が含まれますが、X p 内のすべてのグラフが森であるとは限りません。たとえば_、 X 1_は7 つの頂点を持つ木と三角形K ₃の 2 つのグラフで構成されています。ただし、 X _p内の木の集合は正確に特徴付けることができます。これらの木は、X _{p − 1}内の 3 つの木から、新しいルート頂点を、3 つのより小さな木のそれぞれで任意に選択された頂点にエッジで接続することによって形成できる木です。たとえば、X _{1内の 7 つの頂点を持つ木は、このようにして}X ₀内の 2 つの頂点を持つ木 (単一のエッジ) から形成されます。この構成に基づいて、 X _p内の禁止マイナーの数は少なくとも( p !) ^{2 で}あることが示されます。^{[ 44 ]}パス幅 2 のグラフの禁止マイナーの完全な集合X ₂が計算されており、110 種類の異なるグラフが含まれています。^{[ 45 ]}

マイナー閉グラフ族のグラフ構造定理は、任意のそのような族 F に対して、Fのグラフは、有界種数の曲面に埋め込むことができるグラフのクリーク和に分解でき、クリーク和の各成分には有界数の頂点と渦が存在することを述べている。頂点は、その成分内の他の任意の頂点に隣接できる頂点であり、渦は、有界種数の埋め込みの成分の面の 1 つに接着される有界パス幅のグラフである。渦が埋め込まれる面の周りの頂点の巡回順序は、渦のパス分解と互換性がなければならない。つまり、サイクルを破って線形順序を形成すると、有界頂点分離数を持つ順序になる必要がある。^{[ 4 ]}パス幅が任意のマイナー閉グラフ族と密接に関連しているこの理論は、重要なアルゴリズム的応用がある。^{[ 46 ]}

VLSI設計において、頂点分離問題はもともと回路をより小さなサブシステムに分割し、サブシステム間の境界に少数のコンポーネントを配置する方法として研究された。^{[ 34 ]}

大槻ら（1979）は、ネットのシステムによって相互接続される必要のあるモジュールの集合で構成されるVLSI回路の一次元レイアウトに必要なトラック数をモデル化するために、区間厚を使用している。彼らのモデルでは、頂点がネットを表し、2つの頂点が、それらのネットが両方とも同じモジュールに接続されている場合にエッジで接続されるグラフを形成する。つまり、モジュールとネットがハイパーグラフのノードとハイパーエッジを形成すると解釈される場合、それらから形成されるグラフはその線グラフである。この線グラフのスーパーグラフの区間表現とスーパーグラフの色付けは、水平トラックのシステム（色ごとに1つのトラック）に沿ったネットの配置を記述し、モジュールをトラックに沿って直線的に配置して適切なネットに接続できるようにする。区間グラフが完全グラフであるという事実^{[ 47 ]}は、このタイプの最適な配置に必要な色の数が、ネットグラフの区間完成のクリーク数と同じであることを意味します。

ゲートマトリックスレイアウト^{[ 48 ]}は、ブール論理回路用のCMOS VLSIレイアウトの特定のスタイルです。ゲートマトリックスレイアウトでは、信号は「ライン」（垂直線分）に沿って伝搬され、回路の各ゲートは水平線分に沿って配置される一連のデバイスフィーチャによって形成されます。したがって、各ゲートの水平線分は、ゲートの入力または出力を形成する各ラインの垂直線分と交差する必要があります。大槻ら（1979）のレイアウトと同様に、ラインを配置する垂直トラックの数を最小化するこのタイプのレイアウトは、ラインを頂点とし、ゲートを共有するラインのペアをエッジとするグラフのパス幅を計算することによって見つけることができます。^{[ 49 ]}同じアルゴリズムアプローチは、プログラマブルロジックアレイの折り畳み問題をモデル化するためにも使用できます。^{[ 50 ]}

パス幅はグラフ描画においていくつかの用途があります。

• 与えられた交差数を持つ最小グラフのパス幅は、その交差数の関数によって制限される。^{[ 51 ]}
• 木の頂点を辺の交差なしに描画できる平行線の数は（隣接する頂点を線の列に対して配置する方法に関するさまざまな自然な制約の下で）木のパス幅に比例する。^{[ 52 ]}
• グラフGのk交差h層描画とは、Gの頂点をh個の異なる水平線上に配置し、これらの線の間に単調多角形パスとして辺をルーティングし、交差が最大でk個となるようにしたものです。このような描画を持つグラフのパス幅は、 hとkの関数によって制限されます。したがって、hとk が両方とも定数の場合、グラフがk交差h層描画を持つかどうかを線形時間で判定することが可能です。^{[ 53 ]}
• n個の頂点とパス幅pを持つグラフは、 2 つのエッジ (グリッド点間の直線セグメントとして表される) が互いに交差しないように、 p × p × nサイズの 3 次元グリッドに埋め込むことができます。したがって、有界パス幅のグラフは、線形体積を持つこの種の埋め込みを持ちます。^{[ 54 ]}

高水準プログラミング言語のコンパイルにおいて、パス幅は、直線コード（つまり、制御フローの分岐やループのないコード）のシーケンスを、コード内で計算されたすべての値をメインメモリにスピルアウトする代わりにマシンレジスタに格納できるように並べ替える問題で発生します。このアプリケーションでは、コンパイル対象のコードを、ノードがコードへの入力値とコード内の操作によって計算された値を表す有向非巡回グラフとして表現します。このDAGのノードxからノードyへのエッジは、値xが操作yへの入力の1つであるという事実を表します。このDAGの頂点のトポロジカル順序は、コードの有効な並べ替えを表し、特定の順序でコードを評価するために必要なレジスタの数は、順序の頂点分離数によって与えられます。^{[ 55 ]}

マシンレジスタの任意の固定数wに対して、直線コードの一部を、最大w 個のレジスタで評価できるように並べ替えることができるかどうかを線形時間で判定することが可能です。なぜなら、トポロジカル順序の頂点分離数が最大wである場合、すべての順序の中で最小の頂点分離はそれより大きくなることはないため、上述の DAG の向きを無視して形成される無向グラフのパス幅は最大 w でなければならないからです。パス幅に関する既知の固定パラメータ追跡可能なアルゴリズムを使用して、これが当てはまるかどうかをテストすることができ、当てはまる場合は、w が定数であるという仮定の下で、線形時間で無向グラフのパス分解を見つけることができます。パス分解が見つかったら、動的計画法を使用して、幅wのトポロジカル順序(存在する場合) を再び線形時間で見つけることができます。^{[ 55 ]}

Kornai & Tuza (1992) は、自然言語処理におけるパス幅の応用について述べています。この応用では、文はグラフとしてモデル化され、頂点は単語を表し、辺は単語間の関係を表します。たとえば、文中で形容詞が名詞を修飾する場合、グラフにはその 2 つの単語の間に辺が存在します。人間の短期記憶の容量が限られているため、^{[ 56 ]} Kornai と Tuza は、このグラフはパス幅に制限がある必要がある (より具体的には、パス幅は最大 6 である必要がある) と主張しています。そうでないと、人間は音声を正しく解析できないからです。

グラフアルゴリズムにおける多くの問題は、グラフのパス分解に対する動的計画法を用いることで、パス幅の小さいグラフ上で効率的に解決できる。 ^{[ 10 ]}例えば、n個の頂点を持つグラフGの頂点の線形順序が与えられ、頂点間隔がwである場合、 Gの最大独立集合をO(2 ^w n )の時間で見つけることができる。^{[ 31 ]}パス幅が制限されたグラフでは、このアプローチにより、パス幅によってパラメータ化された固定パラメータの扱いやすいアルゴリズムが得られる。^{[ 49 ]}このような結果は、木幅によってパラメータ化された同様のアルゴリズムに包含されるため、文献ではあまり見られない。しかし、パス幅は、木幅に基づく動的計画法アルゴリズムにおいても、これらのアルゴリズムの空間計算量を測定する際に現れる。^{[ 11 ]}

同じ動的計画法は、パス幅が無制限のグラフにも適用でき、指数時間でパラメータ化されていないグラフ問題を解くアルゴリズムにつながります。たとえば、この動的計画法のアプローチと、3次グラフのパス幅がn /6  +  o( n ) であるという事実を組み合わせると、3次グラフでは最大独立集合を O(2 ^{n /6  +  o( n )} )の時間で構築でき、これは従来の方法よりも高速です。^{[ 31 ]}同様のアプローチにより、 3次グラフの最大カット問題と最小支配集合問題^{[ 31 ] 、およびその他のいくつかのNP困難な最適化問題[ 57 ]}に対する指数時間アルゴリズムが改善されます。