ツリー幅

グラフ理論では、無向グラフのツリー幅は、グラフがツリーからどれくらい離れているかを非公式に指定する整数です。最小のツリー幅は 1 です。ツリー幅が 1 のグラフは、まさにツリーとフォレストです。ツリー幅が最大で 2 のグラフの例としては、シリーズパラレルグラフがあります。ツリー幅がちょうどkである極大グラフはkツリーと呼ばれ、ツリー幅が最大でkであるグラフは部分kツリーと呼ばれます。^[1]他のよく研究されているグラフ族の多くも、ツリー幅が制限されています。

ツリー幅は、グラフのツリー分解における最大頂点集合のサイズ、グラフの弦完備化における最大クリークのサイズ、グラフ上の追跡回避ゲームの戦略を記述する避難所の最大次数、または互いに接する連結されたサブグラフの集合であるブラムブルの最大次数など、いくつかの同等の方法で正式に定義できます。

ツリー幅は、グラフアルゴリズムのパラメータ化された複雑性分析におけるパラメータとしてよく使用されます。一般的なグラフに対してNP 困難な多くのアルゴリズムは、ツリー幅が定数で制限されると簡単になります。

ツリー幅の概念は、もともとUmberto BertelèとFrancesco Brioschi (1972)によって次元という名前で導入されました。これは後に、異なるグラフパラメータであるHadwiger数 と共有する特性に基づいて、Rudolf Halin (1976)によって再発見されました。その後、 Neil RobertsonとPaul Seymour (1984)によって再び再発見され 、それ以来多くの他の著者によって研究されてきました。^[2]

グラフG = ( V , E )の木分解は、ノードX ₁ , …, X _nを持つ木Tであり、各X _{i は}Vのサブセットであり、次の特性^{[3]を満たします (}ノードという用語は、Gの頂点との混同を避けるために、Tの頂点を指すために使用されます)。

1. すべての集合X _iの和集合はVに等しくなります。つまり、各グラフ頂点は少なくとも 1 つのツリー ノードに含まれます。
2. X _iとX _{j の}両方に頂点vが含まれている場合、X _iとX _jの間の（一意の）パスにあるTのすべてのノードX _kにもvが含まれます。同様に、頂点v を含むツリー ノードはTの接続されたサブツリーを形成します。
3. グラフ内のすべてのエッジ( v、w )には、 vとw の両方を含むサブセットX _iが存在します。つまり、対応するサブツリーに共通のノードがある場合にのみ、頂点はグラフ内で隣接します。

木分解の幅は、その最大集合 X i のサイズから 1 を引いた値です。グラフG_のツリー幅tw ( G )は、 Gのすべての可能な木分解の中で最小の幅です。この定義では、ツリーのツリー幅を 1 にするために、最大集合のサイズが 1 減少します。

同様に、 Gのツリー幅は、最小のクリーク番号を持つG を含む弦グラフ内の最大クリークのサイズより 1 小さくなります。このクリーク サイズを持つ弦グラフは、少なくとも 1 つの集合X _iに属する 2 つの頂点ごとにエッジをGに追加することで取得できます。

ツリー幅は、グラフ上で定義された特定の追跡-回避ゲームの回避戦略を記述する関数である避難所の観点から特徴付けることもできます。グラフGがツリー幅kを持つのは、次数k + 1で高次の避難所を持たない場合のみです。ここで、次数k + 1の避難所は、G内の最大k個の頂点の各集合X をG \ Xの連結成分の 1 つにマッピングし、 X ⊆ Yの場合は常にβ ( Y ) ⊆ β ( X )という単調性特性に従う関数βです。

同様の特徴付けは、互いに接する（頂点を共有するか、辺で接続されている）連結サブグラフの族であるブラムブル（brambles）を使用して行うこともできます。 ^[4]ブラムブルの順序はサブグラフの族の最小のヒットセットであり、グラフのツリー幅はブラムブルの最大順序より1小さくなります。

すべての完全グラフ K _{n は}ツリー幅n – 1を持ちます。これは、弦グラフにおけるツリー幅の定義を使用すると最も簡単にわかります。つまり、完全グラフは既に弦グラフであり、エッジを追加しても最大のクリークのサイズを縮小することはできません。

少なくとも 2 つの頂点を持つ連結グラフのツリー幅は、それがツリーである場合に限り 1 になります。ツリーのツリー幅が 1 になるのは、完全グラフの場合と同じ理由からです (つまり、弦があり、最大クリーク サイズが 2 であるため)。逆に、グラフにサイクルがある場合、グラフの弦完備化には、サイクルの連続する 3 つの頂点からなる三角形が少なくとも 1 つ含まれ、そのツリー幅は少なくとも 2 になります。

任意の固定定数kに対して、木幅が最大でkのグラフは部分k木と呼ばれます。木幅が制限された他のグラフファミリーには、サボテングラフ、疑似フォレスト、シリーズパラレルグラフ、外平面グラフ、ハリングラフ、アポロニアンネットワークなどがあります。^[5]構造化プログラムのコンパイル時に発生する制御フローグラフも木幅が制限されており、レジスタ割り当てなどの特定のタスクを効率的に実行できます。^[6]

平面グラフは木幅が制限されていない。なぜなら、 n × n の グリッドグラフは木幅がちょうどnの平面グラフだからである。したがって、F が木幅が制限されたマイナー閉グラフ族である場合、それはすべての平面グラフを含むことはできない。逆に、ある平面グラフが族Fのグラフのマイナーとして出現できない場合、 Fのすべてのグラフの木幅が最大でkになるような定数kが存在する。つまり、次の 3 つの条件は互いに同等である。^[7]

1. F は、制限された木幅のグラフのマイナー閉族です。
2. F を特徴付ける有限個の禁制小数点のうちの 1 つは平面である。
3. F は、すべての平面グラフを含まないマイナー閉グラフ族です。

kの有限値ごとに、木幅が最大kのグラフは、禁制マイナーの有限集合によって特徴付けられる場合があります。(つまり、木幅> kのグラフには、集合内のグラフの 1 つがマイナーとして含まれます。) これらの禁制マイナーの集合のそれぞれには、少なくとも 1 つの平面グラフが含まれます。

• k = 1の場合、唯一の禁制マイナーグラフは3頂点閉路グラフである。^[5]
• k = 2の場合、唯一の禁制マイナーグラフは4頂点完全グラフ K ₄である。^[5]
• k = 3の場合、禁制のマイナーグラフは4つあります。K ₅ 、八面体のグラフ、五角柱 グラフ、ワグナーグラフです。これらのうち、2つの多面体グラフは平面グラフです。^[8]

kの値が大きくなると、禁制マイナーの数は少なくともkの平方根の指数と同じ速さで増加します 。^[9]しかし、禁制マイナーのサイズと数に関する既知の上限は、この下限よりもはるかに高いです。^[10]

与えられたグラフGのツリー幅が最大で与えられた変数kであるかどうかを判断することは NP 完全です。^[11] しかし、k が任意の固定定数である場合、ツリー幅kのグラフを認識し、それらの幅k のツリー分解を線形時間で構築できます。 ^{[12]このアルゴリズムの}kへの時間依存性は指数的です。

膨大な数の分野で木幅が果たす役割のため、グラフの木幅を計算する様々な実用的および理論的なアルゴリズムが開発されてきた。手持ちのアプリケーションに応じて、より優れた近似比、または入力のサイズまたは木幅からの実行時間のより優れた依存性を優先することができる。以下の表は、木幅アルゴリズムのいくつかの概要を示したものである。ここで、kは木幅、n は入力グラフGの頂点数である 。各アルゴリズムは、時間f ( k ) ⋅ g ( n )で、近似値の列に与えられた幅の分解を出力します。たとえば、 Bodlaender (1996) のアルゴリズムは、時間2 O ( k 3 ) ⋅ n で、入力グラフ G の幅が最大 k の木分解を構築するか、 G の木幅が k より大きいことを報告します。同様に、 Bodlaender らのアルゴリズムは、時間 2 ^{O ( k 3 )} ⋅ nで、入力グラフGの幅が最大kのツリー分解を構築するか、 Gの木幅がkより大きいことを報告します。 (2016)は、 2 ^{O ( k )} ⋅ n時間で、入力グラフ Gの幅が最大5 k + 4のツリー分解を構築するか、 Gのツリー幅がkより大きいことを報告します。Korhonen (2021) は、同じ実行時間で これを2 k + 1に改善しました。

平面グラフのツリー幅を決定することがNP完全であるかどうか、あるいはそのツリー幅が多項式時間で計算できるかどうかは不明である。 ^[13]

実際には、Shoikhet & Geiger (1997) のアルゴリズムは、最大 100 個の頂点と最大 11 個のツリー幅を持つグラフのツリー幅を決定し、最適なツリー幅を持つこれらのグラフの弦完備を見つけることができます。

より大きなグラフの場合は、分岐限定探索(BnB) や最良優先探索などの検索ベースの手法を使用してツリー幅を計算できます。これらのアルゴリズムはいつでも実行でき、早期に停止するとツリー幅の上限を出力します。

ツリー幅を計算するための最初の BnB アルゴリズムは、QuickBB アルゴリズム^[14]と呼ばれ、Gogate と Dechter によって提案されました。^[15] BnB アルゴリズムの品質は、使用される下限の品質に大きく依存するため、Gogate と Dechter ^[15]は、ツリー幅の下限を計算するための新しいアルゴリズムである minor-min-width も提案しました。^{[15]大まかに言うと、minor-min-width アルゴリズムは、グラフのツリー幅が最小次}数またはマイナーよりも大きくなることはないという事実を組み合わせて、ツリー幅の下限を生成します。minor-min-width アルゴリズムは、最小次数の頂点とその近傍の 1 つとの間の辺を縮小して、頂点が 1 つだけになるまで繰り返しグラフのマイナーを構築します。構築されたこれらのマイナーの最小次数の最大値は、グラフのツリー幅の下限であることが保証されます。

DowとKorf ^[16]は、最良優先探索法を用いてQuickBBアルゴリズムを改良した。特定のグラフでは、この最良優先探索法はQuickBBよりも1桁高速である。

1970年代初頭、グラフ上で定義された多くの組み合わせ最適化問題は、グラフの次元が有限である限り、非シリアルな動的計画法によって効率的に解くことができることが観察されました。 ^[17]このパラメータは、Bodlaender (1998) によってツリー幅と同等であることが示されました。その後、1980年代末に数人の著者が独立して、^{[18]任意のグラフに対して}NP完全である多くのアルゴリズム問題は、これらのグラフのツリー分解を使用して、ツリー幅が有限のグラフに対して動的計画法によって効率的に解くことができることを観察しました。

一例として、木幅kのグラフの色付けの問題は、グラフの木分解に対して動的計画法アルゴリズムを使用することで解決できる場合があります。木分解の各セットX _iと、X _iの頂点の色クラスへの 各パーティションについて、アルゴリズムは、それらのノードで計算され保存された同様のタイプの情報を組み合わせることで、その色付けが有効であり、木分解内のすべての子孫ノードに拡張できるかどうかを判断します。結果として得られるアルゴリズムは、n頂点グラフの最適な色付けをO ( k ^{k + O (1)} n )時間で見つけます。この時間制限により、この問題は固定パラメータで処理可能になります。

大規模なクラスの問題では、一定の制限付きツリー幅を持つツリー分解が与えられていれば、そのクラスの問題を線形時間で解くアルゴリズムが存在します。具体的には、クールセルの定理^{[19]は、グラフの問題が}モナディック2階論理を使用してグラフの論理で表現できる場合、制限付きツリー幅を持つグラフ上で線形時間で解くことができると述べています。モナディック2階論理は、次の構成を使用してグラフの特性を記述する言語です。

• 論理演算、例えば${\displaystyle \wedge,\vee,\neg,\Rightarrow}$
• 所属検定、例えばe ∈ E、v ∈ V
• 頂点、辺、頂点の集合、および/または辺の集合に対する量化、例えば∀ v ∈ V、∃ e ∈ E、∃ I ⊆ V、∀ F ⊆ E
• 隣接性テスト ( u はeのエンドポイントである)、および最適化などを可能にするいくつかの拡張機能。

たとえば、グラフの3 色塗り問題を考えてみましょう。グラフG = ( V , E )の場合、この問題は、隣接する 2 つの頂点に同じ色が割り当てられないように、各頂点v ∈ Vに 3 色のいずれかを割り当てることができるかどうかを尋ねます。この問題は、次のようにモナド 2 階論理で表現できます。

${\displaystyle \exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge }$

${\displaystyle \forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))}$、

ここで、W ₁、W ₂、W _{3 は}、3 つの色のそれぞれを持つ頂点のサブセットを表します。したがって、Courcelle の結果により、一定の木幅を持つ木分解が与えられたグラフでは、3 色付け問題は線形時間で解決できます。

グラフのパス幅は、木分解による木幅と非常によく似た定義を持ちますが、分解の基礎となる木がパスグラフである木分解に制限されます。あるいは、パス幅は、弦グラフからの木幅の定義に類似して、区間グラフから定義できます。結果として、グラフのパス幅は常にその木幅以上の大きさですが、対数係数でのみ大きくなります。^[5]もう1つのパラメータであるグラフ帯域幅は、適切な区間グラフからの類似の定義を持ち、少なくともパス幅以上の大きさです。その他の関連するパラメータには、木深度、つまり、族がパスを除外する場合に限り、マイナー閉グラフ族に対して制限される数値、および退化、つまり、最大でその木幅に等しいグラフのスパース性の尺度があります。

n × n のグリッドグラフのツリー幅はnなので、グラフGのツリー幅は常にGの最大の正方グリッドマイナーのサイズ以上になります。逆に、ロバートソンとシーモアのグリッドマイナー定理は、最大の正方グリッドマイナーのサイズが少なくとも f ( r )であるような無制限の関数fが存在することを示しています。ここでrはツリー幅です。^[20] fに関する既知の最良の境界は、ある固定定数d > 0に対してf が少なくともΩ( r ^d )であり、最大で^[21]であることです。

${\displaystyle O\left({\sqrt {r/\log r}}\right).}$

下限のΩ表記については、 big O表記を参照してください。制限されたグラフ族ではより厳しい境界が知られており、二次元理論を通じてそれらの族上の多くのグラフ最適化問題に対する効率的なアルゴリズムにつながります。^[22] Halinのグリッド定理は、無限グラフのツリー幅とグリッドマイナーサイズの関係に類似しています。^[23]

部分グラフの取得に関して閉じているグラフの族F は、族内のグラフのツリー幅がそれらの直径の関数によって上限が定められている場合、境界付きローカルツリー幅、または直径-ツリー幅特性を持っていると言われます。クラスがマイナーの取得に関しても閉じていると仮定すると、Fの禁止マイナーの 1 つが頂点グラフである場合に限り、F は境界付きローカルツリー幅を持ちます。^[24]この結果の最初の証明では、頂点マイナーのないグラフ族のツリー幅は直径の関数として最大で二重指数関数的に増加することが示されました。^[25]その後、これは単指数関数的に減少し^[22]、最終的に線形境界になりました。^{[26]境界付きローカルツリー幅は、2 次元の}アルゴリズム 理論と密接に関連しており、^[27]第一階述語論理で定義可能なすべてのグラフ特性は、頂点マイナーのないグラフ族に対して、わずかに超線形な時間で決定できます。^[28]

マイナーグラフの下で閉じていないグラフのクラスでも、局所木幅が制限される可能性がある。特に、これは、直径が制限されたサブグラフがサイズが制限されるため、次数が制限されたグラフのクラスでは自明である。別の例として、 1平面グラフが挙げられる。これは、1辺につき1つの交差を持つ平面上に描画できるグラフであり、より一般的には、1辺につき交差数が制限された、種数が制限された表面上に描画できるグラフである。局所木幅が制限されたマイナー閉グラフ族と同様に、この特性は、これらのグラフの効率的な近似アルゴリズムへの道を示している。^[29]

Halin (1976) は、ツリー幅を含むS関数と呼ばれるグラフパラメータのクラスを定義しています。グラフから整数へのこれらの関数は、辺のないグラフではゼロであること、マイナー単調であること(関数fは、 HがGのマイナーである場合は常にf ( H ) ≤ f ( G )である場合に「マイナー単調」と呼ばれます)、すべての以前の頂点に隣接する新しい頂点が追加されたときに 1 ずつ増加すること、およびクリーク セパレータの両側にある 2 つのサブグラフから大きい方の値を取ることが要求されます。このようなすべての関数の集合は、要素ごとの最小化と最大化の操作の下で完全な格子を形成します。この格子の最上位要素はツリー幅であり、最下位要素はHadwiger 数、つまり指定されたグラフの最大の完全な マイナーのサイズです。