木の分解

グラフ理論において、ツリー分解とは、グラフのツリー幅を定義し、グラフ上の特定の計算問題を高速化する ために使用できるツリーへのグラフのマッピングです。

木分解はジャンクションツリー、クリークツリー、ジョインツリーとも呼ばれ、確率的推論、制約充足、クエリ最適化、^[1]、行列分解などの問題で重要な役割を果たします。

ツリー分解の概念は、もともとルドルフ・ハリン（1976）によって導入されました。その後、ニール・ロバートソンとポール・シーモア（1984） によって再発見され 、それ以来多くの研究者によって研究されてきました。^[2]

直感的には、木分解は、与えられたグラフGの頂点を木のサブツリーとして表し、G内の頂点は、対応するサブツリーが交差する場合にのみ隣接します。したがって、G はサブツリーの交差グラフのサブグラフを形成します。完全な交差グラフは弦グラフです。

各サブツリーは、グラフの頂点をツリーノードの集合に関連付けます。これを正式に定義するには、各ツリーノードをそれに関連付けられた頂点の集合として表します。したがって、グラフG = ( V , E )が与えられた場合、ツリー分解は( X , T )のペアです。ここで、X = { X ₁ , …, X _n }はVのサブセットの族 (バッグと呼ばれることもあります) であり、T はノードがサブセットX _iであるツリーであり、次のプロパティを満たします。^[3]

1. すべての集合X _iの和集合はV に等しくなります。つまり、各グラフ頂点は少なくとも 1 つのツリー ノードに関連付けられます。
2. グラフ内のすべてのエッジ( v、w )には、 vとw の両方を含むサブセットX _iが存在します。つまり、対応するサブツリーに共通のノードがある場合にのみ、頂点はグラフ内で隣接します。
3. X _iとX _{j の}両方に頂点v が含まれる場合、X _iとX _jの間の (一意の) パスにあるツリーのすべてのノードX _kにもvが含まれます。つまり、頂点vに関連付けられたノードは、 Tの接続されたサブセットを形成します。これは、一貫性、または実行交差プロパティとも呼ばれます。 X _i、X _{j 、}およびX _kがノードであり、X _kがX _iからX _jへのパス上にある場合、と同等に述べることができます。${\displaystyle X_{i}\cap X_{j}\subseteq X_{k}}$

グラフのツリー分解は決して一意ではありません。たとえば、単純なツリー分解では、グラフのすべての頂点が単一のルート ノードに含まれます。

基になるツリーがパス グラフであるツリー分解はパス分解と呼ばれ、これらの特殊なタイプのツリー分解から導出される幅パラメーターはパス幅と呼ばれます。

木幅kの木分解( X , T =( I , F ))は、すべてのに対してであり、すべてのに対してであるとき、滑らかである。^[4]${\displaystyle i\in I:|X_{i}|=k+1}$${\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}$

木分解の幅は、その最大集合 X i のサイズから 1 を引いた値です。グラフG_のツリー幅tw ( G )は、 Gのすべての可能な木分解の中で最小の幅です。この定義では、ツリーのツリー幅が 1 になるように、最大​​集合のサイズが 1 だけ減少します。木分解以外の構造、たとえば弦グラフ、ブランブル、ヘイブンなどから木幅を定義することもできます。

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

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

例として、木幅kのグラフで最大の独立集合を見つける問題を考えてみましょう。この問題を解くには、まず木分解のノードの 1 つを任意にルートとして選択します。木分解のノードX _iについて、D _{i を}X _iから派生する集合X _jの和集合とします。独立集合について、A ( S、i ) がD _iの最大の独立サブセットIのサイズを表し、次の式が成り立つものとします。同様に、隣接するノードのペアX _iとX _jで、X _{i が}木のルートからX _jよりも遠い場合、独立集合について、 B ( S、i、j )がD _iの最大の独立サブセットIのサイズを表し、次の式が成り立つものとします。木を下から上へ走査することで、 これらのA値とB値を計算できます。${\displaystyle S\subset X_{i},}$${\displaystyle I\cap X_{i}=S.}$${\displaystyle S\subset X_{i}\cap X_{j},}$${\displaystyle I\cap X_{i}\cap X_{j}=S.}$

${\displaystyle A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)}$

${\displaystyle B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)}$

ここで、計算における合計はノードX _iの子に対して行われます。 ${\displaystyle A(S,i)}$

各ノードまたはエッジには、これらの値を計算する必要がある最大2 ^k個のセットSがあるため、 kが定数であれば、計算全体にはエッジまたはノードごとに一定の時間がかかります。最大独立セットのサイズは、ルート ノードに格納されている最大値であり、最大独立セット自体は、この最大値から開始してこれらの格納された値をバックトラックすることで見つけることができます (動的プログラミング アルゴリズムの標準どおり)。したがって、木幅が制限されているグラフでは、最大独立セットの問題は線形時間で解決できます。同様のアルゴリズムは、他の多くのグラフの問題にも適用されます。

この動的計画法のアプローチは、機械学習において、木幅が制限されたグラフにおけるビリーフプロパゲーションのためのジャンクションツリーアルゴリズムを介して使用されます。また、木幅を計算して木分解を構築するアルゴリズムにおいても重要な役割を果たします。通常、このようなアルゴリズムでは、木幅を近似し、この近似幅で木分解を構築する最初のステップと、近似木分解で動的計画法を実行して木幅の正確な値を計算する2番目のステップがあります。^[4]

• BramblesとHaven  – グラフのツリー幅を定義する際にツリー分解の代替として使用できる 2 種類の構造。
• ブランチ分解 – 幅がツリー幅の定数倍以内である密接に関連した構造。
• 分解法 - ツリー分解は、制約充足問題を解決するための分解法で使用されます。