樹幅

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

平面グラフには木幅の制限はありません。${\displaystyle n\times n}$グリッドグラフは、ツリー幅がちょうど${\displaystyle n}$したがって、${\displaystyle F}$は、木幅が制限されたマイナー閉グラフ族であり、すべての平面グラフを含むことはできません。逆に、ある平面グラフが族内のグラフのマイナーとして出現できない場合${\displaystyle F}$すると定数が${\displaystyle k}$すべてのグラフが${\displaystyle F}$最大で木の幅を持つ${\displaystyle k}$つまり、次の３つの条件は互いに同等である。^{[ 7 ]}

1. ${\displaystyle F}$は、木幅が制限されたグラフのマイナークローズド族である。
2. 有限個の禁止マイナーの1つで、${\displaystyle F}$平面である。
3. ${\displaystyle F}$これは、すべての平面グラフを含まない、マイナーな閉グラフ族です。

有限値ごとに${\displaystyle k}$、ツリー幅が最大で${\displaystyle k}$有限個の禁止マイナーによって特徴付けられる可能性がある。（つまり、木幅がより大きい任意のグラフは、${\displaystyle k}$（セット内のグラフの 1 つをマイナーとして含む。）これらの禁止マイナーの各セットには、少なくとも 1 つの平面グラフが含まれます。

• のために${\displaystyle k=1}$唯一の禁止マイナーは3頂点サイクルグラフである。^{[ 5 ]}
• のために${\displaystyle k=2}$唯一の禁止マイナーは4頂点完全グラフである。${\displaystyle K_{4}}$[ ^{5 ]​}
• のために${\displaystyle k=3}$禁止されている未成年者は4人います。${\displaystyle K_{5}}$正八面体のグラフ、五角柱のグラフ、およびワグナーグラフ。これらのうち、2つの多面体グラフは平面である。^{[ 8 ]}

より大きな値の場合${\displaystyle k}$禁止されている未成年者の数は、少なくとも指数関数的に増加する。${\displaystyle {\sqrt {k}}}$^{[ 9 ]}しかし、禁止マイナーのサイズと数の既知の上限は、この下限よりもはるかに高い。^{[ 10 ]}

それは${\displaystyle {\mathsf {NP}}}$-与えられたグラフが${\displaystyle G}$ツリー幅は最大で特定の変数です${\displaystyle k}$[ ^{11 ]} しかし^、${\displaystyle k}$は任意の固定定数であり、木幅を持つグラフ${\displaystyle k}$認識可能であり、幅${\displaystyle k}$線形時間で構築されたツリー分解。^{[ 12 ]}このアルゴリズムの時間依存性は${\displaystyle k}$指数関数的である。

ツリー幅は膨大な数の分野で重要な役割を果たしているため、グラフのツリー幅を計算するさまざまな実用的および理論的なアルゴリズムが開発されてきました。対象となるアプリケーションに応じて、近似比の向上、または実行時間における入力サイズやツリー幅への依存性の向上を優先することができます。以下の表は、いくつかのツリー幅アルゴリズムの概要を示しています。${\displaystyle k}$は木の幅で、${\displaystyle n}$は入力グラフの頂点の数です。${\displaystyle G}$各アルゴリズムは時間内に出力します${\displaystyle f(k)\cdot g(n)}$近似列に示されている幅の分解。例えば、Bodlaender (1996)のアルゴリズムでは、${\displaystyle 2^{O(k^{3})}\cdot n}$入力グラフのツリー分解を構築する${\displaystyle G}$最大幅${\displaystyle k}$または、木の幅が${\displaystyle G}$より${\displaystyle k}$同様に、 Bodlaender et al. (2016)のアルゴリズムは 時間的に${\displaystyle 2^{O(k)}\cdot n}$入力グラフのツリー分解を構築する${\displaystyle G}$最大幅${\displaystyle 5k+4}$または、木の幅が${\displaystyle G}$より${\displaystyle k}$コルホネン（2021）は分解の幅を改善し、${\displaystyle 2k+1}$同じ上映時間で。

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

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

より大きなグラフの場合、分岐限定法などの探索ベースの手法を使用して木幅を計算できます。これらのアルゴリズムは、途中で停止すると木幅の上限を出力するため、いつでも実行可能です。この種のアルゴリズムは、2004 年に Vibhav Gogate とRina Dechterによって提案されました。この探索の分岐の木幅の下限を提供するために、最小次数頂点とその隣接頂点の間のエッジを繰り返し縮約して、1 つの頂点だけが残るまでグラフマイナーを構築します。これらの構築されたマイナーの最小次数の最大値は、グラフの木幅の下限であることが保証されます。^{[ 14 ]} Alex Dow と Rich Korf は、最良優先探索を使用してこのアルゴリズムをさらに改善しました。^{[ 15 ]}

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

例えば、木幅のグラフを彩色する問題${\displaystyle k}$グラフの木分解に対して動的計画法アルゴリズムを使用することで解決できる可能性がある。各バッグについて${\displaystyle X_{i}}$ツリー分解の、頂点の各分割${\displaystyle X_{i}}$アルゴリズムは、色クラスに色分けし、その色分けが有効かどうかを判断し、同様のタイプの情報を計算してそれらのノードに格納することで、ツリー分解のすべての子孫ノードに拡張できるかどうかを判断します。結果として得られるアルゴリズムは、最適な色分けを見つけます。${\displaystyle n}$-時間軸上の頂点グラフ${\displaystyle O(k^{k+O(1)}n)}$この問題が固定パラメータで扱いやすくなるような時間制限。

大規模な問題クラスについては、一定の有界ツリー幅を持つツリー分解が与えられれば、そのクラスの問題を線形時間で解くアルゴリズムが存在します。具体的には、 Courcelleの定理^{[ 18 ]}は、グラフ問題が単項二階論理を用いたグラフの論理で表現できる場合、有界ツリー幅を持つグラフ上で線形時間で解けることを示しています。単項二階論理は、以下の構成要素を用いてグラフの特性を記述する言語です。

• 論理演算、例えば${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$
• 会員資格テスト、例えば${\displaystyle e\in E}$、${\displaystyle v\in V}$
• 頂点、辺、頂点の集合、および/または辺の集合に対する量化、例えば、${\displaystyle \forall v\in V}$、${\displaystyle \exists e\in E}$、${\displaystyle \exists I\subset V}$、${\displaystyle \forall F\subset E}$
• 頂点-エッジの衝突判定（${\displaystyle u}$は、${\displaystyle e}$）、そして最適化などを可能にする拡張機能もいくつかあります。

例えば、グラフの3彩色問題を考えてみましょう。グラフの場合${\displaystyle G=(V,E)}$この問題では、各頂点に値を割り当てることが可能かどうかを尋ねています。${\displaystyle v\in V}$隣接する2つの頂点に同じ色が割り当てられないように、3つの色のうちの1つを割り当てる。この問題は、単項2階論理で次のように表現できる。 $${\displaystyle \exists W_{1}\subseteq V\ \exists W_{2}\subseteq V\ \exists W_{3}\subseteq V\ \left({\begin{aligned}&\forall v\in V\ (v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge {}\\&\operatorname {independent} (W_{1})\wedge {}\\&\operatorname {independent} (W_{2})\wedge {}\\&\operatorname {independent} (W_{3})\\\end{aligned}}\right),}$$ どこ${\displaystyle W_{1}}$、${\displaystyle W_{2}}$、${\displaystyle W_{3}}$は、3 つの色のそれぞれを持つ頂点のサブセットを表し、部分式は${\displaystyle \operatorname {independent} (W_{i})}$定義される意味は $${\displaystyle \operatorname {independent} (W_{i})\equiv \forall e\in E\ \exists v\in V\ (\operatorname {endpoint} (v,e)\wedge \neg v\in W_{i}).}$$ （この式には、集合が${\displaystyle W_{i}}$互いに素である。）したがって、Courcelleの結果によれば、有界定数ツリー幅の木分解が与えられたグラフに対して、3彩色問題は線形時間で解くことができる。

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

木の幅は${\displaystyle n\times n}$グリッドグラフは${\displaystyle n}$グラフのツリー幅${\displaystyle G}$常に最大の正方形グリッドのサイズ以上である${\displaystyle G}$反対方向には、ロバートソンとシーモアによるグリッドマイナー定理は、非有界関数が存在することを示している。${\displaystyle f}$木幅のグラフの最大の正方形グリッドマイナー${\displaystyle k}$少なくともサイズがあります${\displaystyle f(k)}$[ ^{19 ]}既知の最良の境界^は${\displaystyle f}$それは${\displaystyle f}$少なくとも${\displaystyle \Omega (k^{d})}$ある固定定数に対して${\displaystyle d>0}$、そして最大で^{[ 20 ]}$${\displaystyle O\left({\sqrt {r/\log r}}\right).}$$

（${\displaystyle \Omega }$下限の表記については、ビッグ O 表記を参照してください。）制限付きグラフ族についてはより厳しい境界が知られており、二次元性の理論を通じて、これらの族上の多くのグラフ最適化問題に対する効率的なアルゴリズムにつながっています。^{[ 21 ]}ハリンのグリッド定理は、無限グラフのツリー幅とグリッドマイナーサイズの関係の類似物を提供します。^{[ 22 ]}

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

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

Halin (1976) は、木幅を含むS関数と呼ばれるグラフパラメータのクラスを定義しました。グラフから整数へのこれらの関数は、エッジのないグラフではゼロであり、マイナー単調（関数）である必要があります。${\displaystyle f}$マイナーモノトーンと呼ばれるのは、${\displaystyle H}$未成年者${\displaystyle G}$1つは${\displaystyle f(H)\leq f(G)}$）は、すべての以前の頂点に隣接する新しい頂点が追加されたときに 1 ずつ増加し、クリーク区切り線の両側の 2 つのサブグラフから大きい方の値を取得します。このようなすべての関数の集合は、要素ごとの最小化と最大化の操作の下で完全な格子を形成します。この格子の最上位要素は木幅であり、最下位要素はハドウィガー数、つまり与えられたグラフの中で最大の完全なマイナーのサイズです。