分解法（制約充足）

制約充足問題において、分解法は制約充足問題を、二項非巡回的な別の制約充足問題へと変換します。分解法は、変数を集合にグループ化し、各集合について部分問題を解くことで機能します。このような変換が行われるのは、二項非巡回問題の解法が扱いやすい問題であるためです。

それぞれの構造的制約は、変換後の問題を解く複雑さの尺度を定義し、この尺度は幅と呼ばれます。許容される最大幅を固定することは、制約充足問題のサブクラスを識別する方法の一つです。このクラスの問題を解くことは、ほとんどの分解において多項式式です。もしこれが分解に当てはまるなら、固定幅問題のクラスは制約充足問題の扱いやすいサブクラスを形成します。

概要

分解法は、問題をより解決しやすい新しい問題に変換します。新しい問題は2項制約のみを含み、そのスコープは有向非巡回グラフを形成します。新しい問題の変数はそれぞれ、元の問題の変数の集合を表します。これらの集合は必ずしも互いに素ではありませんが、元の変数の集合をカバーします。この変換により、各変数の集合に関連するすべての部分解が求められます。この変換によって得られる問題は、これらの局所解間の相互作用を表します。

定義により、分解法はバイナリ非巡回問題を生成します。このような問題は、そのサイズの多項式時間で解くことができます。結果として、元の問題は、まず変換してからその結果の問題を解くことで解くことができます。ただし、このアルゴリズムが多項式時間になるのは、分解によってサイズが超多項式的に増加しない場合のみです。分解法の幅は、生成された問題のサイズの尺度です。元々、幅は元の変数の集合の最大基数として定義されていましたが、ハイパーツリー分解という方法では、異なる尺度が使用されています。いずれにしても、分解の幅は、サイズが定数で制限される分解によって過度に大きな問題が発生しないように定義されます。固定幅の分解を持つインスタンスは、分解によって、元のインスタンスのサイズの多項式で制限されるサイズのインスタンスに変換できます。

問題の幅は、その最小幅の分解の幅です。固定幅の分解は問題を効率的に解くために使用できますが、インスタンスの幅の境界は、必然的に扱いやすい構造的制約を生み出します。確かに、固定幅の問題には固定幅の分解がありますが、それを見つけるのは多項式ではないかもしれません。固定幅の問題を分解によって効率的に解くためには、その狭い幅の分解の 1 つを効率的に見つけなければなりません。このため、分解法とそれに関連する幅は、問題の固定幅分解が与えられたときに問題を解くのが多項式時間であるだけでなく、固定幅の問題の固定幅分解を見つけるのも多項式時間であるように定義されます。

分解方法

分解法は、任意の問題から簡単に解ける問題を作成します。この新しい問題の各変数は、元の変数の集合に関連付けられ、その定義域には、関連付けられた集合内の変数の値の組が含まれます。特に、これらの組は、これらの変数に対する一連の制約を満たす組です。新しい問題の制約は、2つの新しい変数の値が、元の変数を共有する2つの組を値として持つように制限します。さらに3つの条件により、新しい問題は古い問題と等価であり、効率的に解くことができます。

新しい問題を効率的に解くためには、新しい問題の主グラフが非巡回であることが必要です。言い換えれば、変数を頂点、（二項）制約を辺と見なすと、結果として得られるグラフは木または森である必要があります。

新しい問題が古い問題と等価であるためには、元の制約のそれぞれが、少なくとも1つの新しい変数の定義域の定義の一部として強制されます。そのためには、古い問題の各制約に対して、新しい問題の変数が存在し、それに関連付けられた元の変数の集合がその制約のスコープを含み、その定義域内のすべてのタプルがその制約を満たす必要があります。

等価性を保証するために必要な更なる条件は、バイナリ制約が各元の変数のすべての「コピー」に同じ値を強制するのに十分であることです。同じ元の変数が複数の新しい変数に関連付けられる可能性があるため、これらの新しい変数の値はすべて、古い変数の値と一致している必要があります。バイナリ制約は、2つの新しい変数間で共有される古い変数の等価性を強制するために使用されます。新しい変数の2つのコピーは、それらの新しい変数間にバイナリ制約のパスが存在し、このパス内のすべての新しい変数に古い変数が含まれている場合、強制的に等価になります。

	制約充足問題の例。この問題はバイナリであり、制約はこのグラフのエッジによって表されます。
	分解木。元のグラフのすべての辺には、その両端を含むノードが存在する。変数を含むすべてのノードは接続されている。
	部分問題を解く。この例では、最初の集合の変数に対するすべての制約からなる部分問題を解く方法を示します。同様の手順を他の集合についても行います。 $\{x,y,z\}$ $\{u,x,z\}$ $\{y,w\}$
	木の各ノードは変数になります。その定義域は部分問題の解の集合、つまりタプルの集合です。新しい問題の制約は、元の変数と等しい値を持つタプルのみを許可します。図では、の等価性が示されています。対応する制約は、の最初のタプルとの最初のタプル、およびの2番目のタプルとの2番目のタプルによってのみ満たされます。さらに、の2番目のタプルは、左の子（）に満たされるタプルを見つけることができません。したがって、の2番目のタプルは削除する必要があります。 $y$ $(x,y,z)$ $(y,w)$ $(x,y,z)$ $(y,w)$ $(x,y,z)$ $(u,x,z)$ $(u,x,z)$

分解法は通常、新しい問題の変数をノードとするツリーを提供することによって定義されます。各ノードには、関連付けられた元の変数のセットと、場合によっては、新しい問題の変数のドメインを構築するために使用される元の制約のセットも提供されます。上記の 3 つの条件 (ツリー構造、制約の強制、元の変数のコピーの同値性) のうち、最初の条件はこの定義によって自動的に強制されます。制約の強制の条件は、ほとんどの場合、各制約のスコープが、あるノードの変数のサブセットである、と定式化されます。ただし、ノードが制約のセットにも関連付けられている場合は、異なる条件を使用できます。元の変数のすべてのコピーの同値性は、通常、次のように定式化されます。元の変数に関連付けられたノードによって誘導されるサブグラフは接続されている。

バイナリ問題の分解法

分解手法は数多く存在します。そのほとんどは、インスタンスの幅を制限して扱いやすいクラスを生成します。以下は、二項制約充足問題に対して定義されている分解手法です。問題を双対問題に変換するか、隠れ変数を使用することで二項問題にすることができるため、これらの手法は間接的に任意の制約充足問題の木分解を提供するために使用できます。

二重連結成分

グラフ理論において、分離頂点とは、グラフから削除されるとグラフを「破壊する」ノードのことです。正式には、グラフから削除されると、その接続されたコンポーネントの数が増加するノードです。グラフの2連結コンポーネントとは、誘導された部分グラフが接続され、分離頂点を持たないノードの最大集合です。グラフ理論では、グラフの2連結コンポーネントと分離頂点は木を形成することが知られています。この木は次のように構築できます。ノードはグラフの2連結コンポーネントと分離頂点であり、辺は2連結コンポーネントと分離頂点のみを接続します。特に、頂点がコンポーネントに含まれている場合、このようになります。このグラフが実際に木であることが証明できます。

二項制約充足問題における制約を、変数をノードとするグラフの辺と見なすと、この木は問題の分解となる。分解の幅は、二項連結成分の頂点の最大数である。


制約充足問題の原始グラフ（各ノードは変数を表し、各エッジは2つの変数間の制約を表します）	その二連結成分（色付き）とそれを分離する頂点（黒、この場合は1つのみ）	二連結分解：木のノードは頂点と二連結成分を分離する

サイクルカットセット

サイクル分解法は、問題を循環部分と非循環部分に分割します。この方法は、ノードにノード集合のラベルが付けられた木を生成する他の分解法の定義には当てはまりませんが、そのような用語で簡単に再定式化できます。

この分解法は、いくつかの変数に値を設定した後、それらの変数を取り除いた後に残る問題は非巡回的になる可能性があるという考えに基づいています。正式には、グラフのサイクルカットセットとは、グラフから削除されたときにグラフを非巡回化するノードの集合です。制約充足問題についても、その主グラフを用いて同様の定義を与えることができます。サイクル分解の幅は、カットセット内の変数の数です。問題の幅は、サイクルカットセット分解の最小幅です。


制約充足問題のグラフ表現	グラフのサイクルカットセット（他にも存在する）	循環カットセットを削除すると、残るのは非巡回グラフ（この場合は木だが、一般的には森）である。

ノードbをルートとして選択すると、これは他の分解方法で作成されたものと同様のツリーになります。

このような分解は、他の分解のスキームには適合しません。分解の結果はツリーではなく、変数の集合 (カットセットの変数) とツリー (カットセットにない変数によって形成される) であるためです。ただし、他の分解方法で生成されるツリーと同様のツリーは、カットセットを削除して得られるツリーから取得できます。これは、ルートを選択し、カットセットのすべての変数をそのすべてのノードに追加し、各ノードの変数をそのすべての子に追加することで行われます。この結果、ノードに関連付けられた変数の最大数がカットセットのサイズに 2 を加えた数に等しいツリーが生成されます。2 の追加を除けば、これが分解の幅であり、考慮されるカットセット内の変数の数として定義されます。

残念ながら、削除する最小セットを決定することはNP 困難な問題です。

木の分解

木分解はグラフ理論におけるよく知られた概念です。二項制約の観点から再定式化すると、木分解とは、ノードが変数の集合に関連付けられた木構造です。各制約のスコープは、あるノードの変数の集合に含まれ、各変数に関連付けられたノードのサブツリーは連結されています。これは、上記のスキームに従う二項制約の最も一般的な分解形式です。木に課される条件は、元の問題と新しい問題の等価性を保証するために必要な条件のみであるためです。

このような分解の幅は、同じノードに関連付けられた変数の最大数から1を引いた値です。問題のツリー幅は、ツリー分解の最小幅です。

バケット消去は、特定の木構造に基づくアルゴリズムとして再定式化できます。具体的には、変数の順序付けが与えられた場合、各変数は、そのスコープ内で最大の制約を含むバケットに関連付けられます。バケット消去は、各バケットにノードを持つ木構造に対応します。このノードには、そのすべての制約が関連付けられており、これらの制約のすべての変数の集合に対応します。のバケットに関連付けられたノードの親は、のバケットに関連付けられたノードです。ここで、は制約内で最大のノードであり、順序付けではが先行します。 $x_{i}$ $x_{j}$ $x_{j}$ $x_{i}$ $x_{i}$

任意の問題に対する分解法

以下の手法は、任意の制約充足問題（二項問題を含む）を変換するために使用できます。これらの手法は二項問題にも使用できるため、制約を二項問題に変換した結果（双対問題に変換するか、隠れ変数を使用するかのいずれか）にも使用できます。

これらの手法の中には、制約をツリーのノードに関連付け、ノードに関連付けられた制約の数を考慮して幅を定義するものがあります。これにより、一部の問題の幅が削減される可能性があります。例えば、各ノードに10個の変数が関連付けられている分解の幅は10ですが、これらの10個の変数のそれぞれが制約のスコープである場合、各ノードにその制約を関連付けることで、幅は1になります。

二重連結成分

任意の制約充足問題の二連結分解は、その主グラフの二連結分解である。各制約は主グラフ上の変数にクリークを形成し、クリークは二連結成分または二連結成分の部分集合のいずれかであるため、木のノードに任意の制約を適用することができる。

木の分解

任意の制約充足問題の木分解は、その主グラフの木分解である。各制約は主グラフ上の変数にクリークを形成し、すべての木分解においてクリークの変数はいずれかのノードの変数に完全に含まれるため、すべての制約は木のノードに適用できる。

サイクルハイパーカットセット

これは、ハイパーグラフのカットセットの定義を用いたサイクルカットセットと同じ方法です。ハイパーグラフのサイクルハイパーカットセットとは、すべての頂点を削除するとハイパーグラフが非循環になるエッジ（頂点ではなく）の集合です。ハイパーカットセットのすべての変数を1つのハイパーカットセットにグループ化することで、分解を得ることができます。これにより、ノードがハイパーエッジの集合であるツリーが生成されます。このような分解の幅は、ノードに関連付けられた集合の最大サイズであり、元の問題が非循環の場合は1、そうでない場合は最小のハイパーカットセットのサイズになります。問題の幅は、その分解の最小幅です。

ヒンジ分解

ヒンジとは、以下に定義されるいくつかの特性を持つハイパーグラフのノードのサブセットです。ヒンジ分解は、制約充足問題の変数をノードとし、その制約のスコープをハイパーエッジとするハイパーグラフの最小ヒンジとなる変数の集合に基づいています。

ヒンジの定義は以下のとおりです。をハイパーエッジの集合とします。に関するパスとは、各エッジと次のエッジの交差点が空でなく、のノードに含まれないようなエッジの列です。エッジの集合がに関して連結されている場合、そのエッジの各ペアに対して、に関するパスが存在し、その2つのノードが最初のエッジと最後のエッジである場合に限ります。に関する連結成分は、に関して連結されたエッジの最大集合です。 $H$ $H$ $H$ $H$ $H$ $H$ $H$

ヒンジは、他のハイパーエッジが含まれないハイパーグラフである、縮約ハイパーグラフに対して定義されます。に関するすべての連結成分について、に含まれるすべてのノードがの単一のエッジに含まれる場合、少なくとも2つのエッジの集合はヒンジと呼ばれます。 $H$ $F$ $H$ $F$ $H$ $H$

ヒンジ分解は、制約充足問題とハイパーグラフとの対応に基づいています。問題に関連付けられたハイパーグラフは、問題の変数をノードとして持ち、制約のスコープをハイパーエッジとして持ちます。制約充足問題のヒンジ分解は、問題に関連付けられたハイパーグラフのいくつかの最小ヒンジをノードとし、他のいくつかの条件を満たすツリーです。問題とハイパーグラフとの対応により、ヒンジは制約のスコープの集合となり、したがって制約の集合と見なすことができます。ヒンジ分解の定義には3つの追加条件があり、そのうち最初の2つは元の問題と新しい問題の等価性を保証します。等価性の2つの条件は、各制約のスコープがツリーの少なくとも1つのノードに含まれること、および元の問題の変数によって誘導されるサブツリーが接続されていることです。追加条件は、2つのノードが結合されている場合、それらは正確に1つの制約を共有し、この制約のスコープには2つのノードで共有されるすべての変数が含まれることです。

ノードの制約の最大数は、同じ問題のすべてのヒンジ分解において同じです。この数は、問題の 循環度、またはヒンジ幅と呼ばれます。

ツリークラスタリング

ツリークラスタリングまたは結合ツリークラスタリングは、結果の問題に結合ツリーが含まれるように制約をマージすることに基づいています。この結合ツリーは分解の結果です。

制約充足問題の結合木とは、各ノードが制約（およびその逆）に関連付けられ、制約に変数が含まれるノードのサブツリーが連結されている木です。したがって、結合木の作成は、木の各ノードが制約のスコープに関連付けられている、ある種の分解と見なすことができます。

すべての制約充足問題が結合木を持つわけではありません。しかし、制約をマージすることで、結合木を持つように問題を修正することは可能です。ツリークラスタリングは、問題が結合木を持つためには、その主グラフが弦状であり、かつ問題に適合している必要があるという条件に基づいています。弦状とは、主グラフのすべての極大クリークの変数が制約のスコープであり、その逆もまた同様であることを意味します。ツリークラスタリングは、これらの2つの条件を満たすように任意の問題を修正します。弦性は、新しい2項制約を追加することで強化されます。適合性は、制約をマージすることで得られます。

特に、弦性は、問題にいくつかの「偽の」二項制約を追加することで強化されます。これらの二項制約は、任意の値のペアが満たす二項制約であり、問題の主グラフに辺を追加するためだけに使用されます。特に、弦性は、任意の順序に従って主グラフの誘導グラフを生成する辺を追加することで実現されます。この手順は正しいです。なぜなら、誘導グラフは常に弦性を持ち、元のグラフに辺を追加することで得られるからです。

共形性は、主グラフ上の極大クリークが制約条件のスコープと正確に一致することを要求する。すべての元の制約条件のスコープは主グラフ上のクリークであるが、このクリークは必ずしも極大であるわけではない。さらに、たとえ当初極大であったとしても、弦性を適用することでより大きなクリークが生成される可能性がある。共形性は、制約条件をマージすることによって実現される。特に、弦性を適用した結果生じるグラフ上のすべての極大クリークに対して、そのクリークをスコープとする新しい制約条件が生成される。この新しい制約条件を満たす値は、そのクリークにスコープが含まれるすべての元の制約条件を満たす値である。この変換により、すべての元の制約条件は少なくとも1つの新しい制約条件に「含まれる」。実際、すべての元の制約条件のスコープは主グラフ上のクリークである。このクリークは弦性を適用した後もクリークのままである。これは、この処理によって新しいエッジが導入されるだけであるためである。結果として、このクリークは極大であるか、極大クリークに含まれるかのいずれかとなる。


例: バイナリ制約充足問題 (結合ツリークラスタリングは非バイナリ制約にも適用できます)。このグラフは弦ではありません (x3x4x5x6 は弦のない 4 つのノードのサイクルを形成します)。	グラフは弦状になっています。アルゴリズムはx6からx1までのノードを分析します。赤いエッジは、x6が結合されていない2つの親を持つ唯一のノードであるため、追加された唯一のエッジです。これは、x4とx5の間の制約を表しており、これはすべての値のペアによって満たされます。	結果のグラフの最大クリークが特定されます。結合木クラスタリングは、{x3, x4, x5, x6} の制約を、{x3, x4, x5} と {x4, x5, x6} の2つの同等の制約に置き換えます。

この変換には、弦グラフの最大クリークを特定する必要があります。しかし、これは弦性を適用するために用いられるのと同じ順序付けを用いて容易に行うことができます。各ノードの親はすべて互いに接続されているため、最大クリークはノード（最大カーディナリティ順序付けにおけるクリークの最大ノード）とそのすべての親から構成されます。したがって、これらの最大クリークは、各ノードとその親を考慮することで検出できます。

このプロセスから得られる問題は結合木を持ち、同じ変数の順序を再び使用することで、このような結合木を得ることができます。最後のノードから最初のノードに向かって進むと、すべての制約は、より多くの変数を共有する前の制約と接続されます。結合木クラスタリングは、次のような分解手法と見なすことができます。

被覆の要素は、弦性を強制することによって生じるグラフのクリークです。
ツリーは結合ツリーです。
すべての制約は、制約のスコープを含む変数セットを持つツリーのすべてのノードに割り当てられます。

ツリークラスタリング分解の幅とは、ツリーの各ノードに関連付けられた変数の最大数です。問題の幅とは、ツリークラスタリング分解の最小幅です。

ヒンジ/クラスタリング分解

ヒンジ分解の結果は、各ヒンジをツリークラスタリングを用いて分解することでさらに簡素化できます。つまり、ヒンジが特定されると、それぞれのツリークラスタリングが生成されます。したがって、結果として得られるツリーでは、各ノードがツリーに置き換えられます。

クエリ分解

クエリ分解は、ツリーの各ノードに変数の集合と制約の集合を関連付けます。各制約はいずれかのノードに関連付けられ、特定の変数または制約に関連付けられたノードによって誘導されるサブツリーが連結されます。より正確には、各変数について、その変数に関連付けられているノード、またはこの変数をスコープに含む制約に関連付けられているノードのサブツリーが連結されます。分解の幅は、ノードに関連付けられている変数と制約の最大合計数です。

制約をノードに関連付けると、分解の幅とインスタンスの幅が減少する可能性があります。一方で、この幅の定義により、分解が与えられていれば、固定幅の問題を多項式時間で解くことが可能です。この場合、新しい変数の領域は、多項式的に大きくなる可能性があるものの、制約の数が固定された部分問題を解くことによって得られます。その結果、この領域は多項式サイズであることが保証されます。新しい問題の制約は、2つの領域の等式であるため、同様に多項式サイズになります。

制約充足問題のハイパーグラフ表現:制約には名前(P, Q, R, S, T)が与えられ、そのスコープが表示されます(P(a, b, c)は制約Pが変数{a, b, c}上にあることを意味します)

問題のクエリ分解。ノードには変数、制約、またはその両方が含まれる場合があります。右端のノードには合計5つの変数（つまり、2つの制約のうちa、b、c、d、e）が関連付けられていますが、どのノードにも3つ以上の制約と独立した変数が含まれていないため、これは幅3の分解です（幅2の分解も存在し、この幅2の分解がこのハイパーグラフの最小幅であることが示せます）。

純粋クエリ分解とは、ノードが制約にのみ関連付けられているクエリ分解です。与えられた幅のクエリ分解から、対数空間において同じ幅の純粋クエリ分解を構築できます。これは、ノードの制約に含まれない変数を、それらの変数を含む制約に置き換えることで得られます。

この分解法の欠点は、インスタンスが固定幅であるかどうかのチェックが一般にNP完全であることだ。これは幅4の場合に当てはまることが証明されている。

ハイパーツリー分解

ハイパーツリー分解は、ツリーの各ノードに変数の集合と制約の集合を関連付けます。これはクエリ分解を拡張し、ノードの制約に、そのノードに関連付けられた新しい変数のドメインを作成する際に使用されない変数を含めることができます。分解法の共通条件（各制約のスコープが少なくともノードに関連付けられた変数の集合内であり、元の変数によって誘導されるサブツリーが連結されていること）に加えて、以下の2つの条件を満たす必要があります。

ノード内の各元の変数は、そのノードに関連付けられた少なくとも 1 つの制約の範囲内にあります。
ノードの制約の変数のうち、そのノードの変数ではないものは、そのノードをルートとするサブツリーには出現しません。

木分解の幅は、各ノードに関連付けられた制約の最大数です。この幅が定数で制限されている場合、元の問題と同等の問題を多項式時間で構築できます。ノードに関連付けられていないが、ノードの制約のスコープ内にある変数は、このインスタンスの構築時に「射影」されます。これは、まず制約をノードの変数に射影し、次にこの部分問題のすべての解を求めるか、最初にすべての制約を適用した部分問題を解いてから余分な変数を削除することで実行できます。

上記のクエリ分解と同じ問題のハイパーツリー分解。R(b,d,e,-)は、Rの最後の変数がルートに関連付けられた変数ではないことを意味します。ルートの1つの制約に2つの変数をグループ化することで、幅は3から2に減少します。

上記の2つの要件は、元の問題と新しい問題の等価性を保証するためには必要ありません。これらは、制限された幅の問題が多項式時間で解けることを保証するために必要です。

制約をノードに関連付ける可能性があるものの、その変数の一部がノードに実際に関連付けられていない場合、クエリの幅よりも狭い幅が生成されることがあります。たとえば、クエリ分解でノードがに関連付けられており、制約が存在する場合、ハイパーツリー分解では同じノードを制約と変数に関連付けることができます。幅のチェックでは制約のみが計算されるため、このノードの幅は2になります。クエリ分解（制約1つと変数3つ）を使用する場合、同じノードの幅は4になります。この幅の縮小は、2つ以上の変数を1つの制約に置き換えることができる場合、たとえこの制約にノードに関連付けられていない変数が含まれていても可能です。 $\{C(a,b),c,d,e\}$ $D(c,d,e,f)$ $\{C,D\}$ $\{a,b,c,d,e\}$

一般化ハイパーツリー分解

一般化ハイパーツリー分解はハイパーツリー分解と同様に定義されますが、最後の要件、すなわち「ノードの制約の変数のうち、そのノードの変数ではないものは、そのノードをルートとする部分木に出現しない」という条件が省略されます。問題の固定幅分解が与えられれば、明らかに多項式時間で解くことができます。しかし、固定幅分解が存在することが分かっていても、それを見つける複雑さが2001年時点では不明であるため、固定幅への制限が扱いやすいかどうかは不明です。

比較

インスタンスの幅は、分解手法の効率性を示す一形態です。実際、問題は固定幅の分解から解くことができるため、分解の幅が狭いほど、その分解を用いて効率的に解けるインスタンスの数が多くなります。

一部の分解では、ノードの変数の数（または同様の量）を幅として使用します。その他の分解では使用しません。サイクルハイパーカットセット、ヒンジ分解、クエリ分解、ハイパーツリー分解、一般化ハイパーツリー分解では、制約（またはハイパーエッジの形式での制約のスコープ）がノードに関連し、ノードに関連付けられた制約の数を幅に含めます。これにより、幅を大幅に節約できます。実際、変数に単一の制約がある問題は、単一のノードを持つツリーにのみ分解できます。このノードは、変数または単一の制約に関連付けることができます。変数の数を数えると幅になり、制約の数を数えると幅になります。 $n$ $n$ $n$ $1$

他のすべての分解手法との比較は、一般化とビートに基づいています。一般化とは、ある手法では幅を持つすべての問題が、一定のに対してで幅が制限されることを意味します。ビートとは、ある分解手法では幅が固定されているものの、別の分解手法では固定されていない問題のクラスが存在することを意味します。以下は、クエリ分解を考慮しない任意の問題に対する結果です。 $n$ $n+k$ $k$

ハイパーツリー分解は一般化され、他のすべての方法よりも優れている
ツリークラスタリングで強化されたヒンジ分解は、ヒンジ分解とツリークラスタリングの両方を一般化し、上回る。
ツリークラスタリングはツリー分解（プライマルグラフ上）と同等である
ヒンジ分解とツリークラスタリングはどちらも一般化され、双連結成分に勝る
サイクルカットセット（プライマルグラフ上）は一般化されており、サイクルハイパーカットセットとツリークラスタリングの両方に勝る。

ツリークラスタリングの幅は、問題の誘導幅に1を加えた値に等しいことも示されます。誘導幅が固定された問題に対する多項式である適応的整合性アルゴリズムは、ツリークラスタリングの最初のステップと同様に、問題を等価な問題に変換します。

分解から解く

分解木が与えられれば、上述のように二分木のような問題を構築し、それを解くことで解くことができます。これは多項式時間問題であり、例えば方向性アークの整合性を強制するアルゴリズムを用いることで多項式時間で解くことができます。

分解によって生じる二項非巡回問題に対応する特殊なアルゴリズムを以下に説明します。このアルゴリズムは、木のエッジに沿って、葉から根へ、そしてまた葉から根へ渡される制約を作成することで機能します。エッジに沿って渡される制約は、エッジの片側にあるグラフの部分におけるすべての制約の効果を、反対側に「まとめる」ものです。

ノード i からノード j に渡される制約は、i の「側」にあるノードが j の変数に与える影響を要約したものです。

木構造において、すべてのエッジはグラフを2つの部分に分割します。エッジに渡される制約は、エッジの始点側が終点ノードの変数にどのように影響するかを示します。言い換えれば、ノードからノードへと渡される制約は、「側」のノードがノードの変数にどのように制約するかを示します。 $i$ $j$ $i$ $j$

これら2つのノードの変数がとである場合、側のノードはすべての変数ではなく、共有変数のみに影響を与えます。その結果、側のノードのへの影響は、変数に対する制約として表現できます。このような制約は、ノードの集合が他のノードにどのように影響を与えるかを示す「要約」と見ることができます。 $X_{i}$ $X_{j}$ $i$ $X_{j}$ $X_{i}\cap X_{j}$ $X_{j}$ $i$ $X_{i}\cap X_{j}$

アルゴリズムは木の葉から処理を進めます。各ノードでは、その子ノード（存在する場合）の要約が収集されます。これらの要約とノードの制約を用いて、親ノードの要約が生成されます。ルートノードに到達すると、処理が反転し、各子ノードの要約が生成され、送信されます。すべての葉ノードに到達すると、アルゴリズムは停止します。


関連する制約を持つ分解木。この例では、すべての変数のドメインは{0,..,10}です。	左端のノードには制約a<bが含まれており、変数bを親ノードと共有しています。これらの制約により、変数bは1以上の値のみを取ることができます。この制約b>0は親ノードに送信されます。	ルートの左の子は制約 b>0 を受け取り、それを自身の制約 b<c と結合します。子は親と c を共有し、2つの制約は c>1 を強制します。この制約は親に送信されます。	ルートはすべての子ノードの制約を受け取ると、それらを結合し、子ノードに制約を返します。このプロセスはすべてのリーフノードに到達した時点で終了します。この時点で、変数に許容される値は明示的です。

2つのノード間で共有される変数の集合は、それらのセパレータと呼ばれます。セパレータはノードに関連付けられた2つの集合の交差であるため、そのサイズはグラフの誘導幅よりも大きくなることはありません。

グラフの幅は各ノードにおける部分問題の解法に必要な時間に影響しますが、セパレータのサイズはノード間で渡される制約のサイズに影響します。実際、これらの制約はセパレータをスコープとしています。その結果、すべての変数のドメインがサイズの場合、セパレータのサイズに関する制約では、サイズを保存する必要がある可能性があります。 $n$ $d^{n}$ $d$

メモリと時間のトレードオフ

分解木から問題を解くアルゴリズムには、2つの操作が含まれます。1つはノードに関連する部分問題を解くこと、もう1つは2つのノード間の共有変数（セパレータ）に関連する制約を作成することです。これらの2つの操作には、それぞれ異なる戦略を使用できます。特に、セパレータに関する制約の作成は、推論の一種である変数消去法を用いて行うことができます。一方、部分問題は探索（バックトラックなど）によって解くことができます。

このアルゴリズムの問題点は、ノード間で渡される制約がセパレータのサイズの指数関数的になる可能性があることです。これらの制約を格納するために必要なメモリは、小さなセパレータを用いたツリー分解を使用することで削減できます。ただし、このような分解ツリーの幅（各ノードのノード数）は、最適な値よりも大きくなる可能性があります。

与えられた分解木において、セパレータの最大許容サイズを固定値で強制するには、セパレータがこのサイズより大きいノードのペアをすべて結合します。2つのノードをマージすると、通常、2つのノードの変数セットよりも大きな変数セットを持つノードが生成されます。これにより、木の幅が増加する可能性があります。ただし、このマージによって、マージされた2つのノード間のセパレータが削除されるだけで、木のセパレータは変更されません。

後者は非循環性の結果です。つまり、結合された2つのノードは、同じ他のノードに結合することはできません。とがマージされる2つのノードであり、とがそれらに結合されたノードの集合である場合、となります。そうでなければ、ツリーに循環が生じます。その結果、とをマージして得られたノードは、の各ノードに結合されます。その結果、このマージされたノードのセパレータは、元の2つのノードのセパレータと全く同じになります。 $n_{1}$ $n_{2}$ $N_{1}$ $N_{2}$ $N_{1}\cap N_{2}=\emptyset$ $n_{1}$ $n_{2}$ $N_{1}\cup N_{2}$

その結果、セパレータで結合されたノードペアをマージしても、他のセパレータは変更されません。そのため、まずすべてのセパレータサイズを計算し、次に指定されたサイズよりも大きいセパレータを持つノードペアを反復的にマージすることで、固定の最大セパレータサイズを強制することができ、実行中にセパレータのサイズを再計算する必要がなくなります。

構造上の制限

分解法の幅を定数で制限すると、構造的制約が生じます。つまり、制約の可能な範囲は制限されますが、それらの関係は制限されません。制約充足の扱いやすいサブクラスを得るための補完的な方法は、制約の関係に制約を課すことです。これは関係制約と呼ばれ、許容される関係の集合は制約言語と呼ばれます。

定数で制限された分解幅を持つ問題を解くことがPに含まれる場合、その分解は扱いやすい構造的制約をもたらす。上述のように、扱いやすさには2つの条件が満たされる必要がある。第一に、問題の幅が定数で制限されている場合、制限された幅の分解は多項式時間で見つけられる。第二に、分解の幅が固定されている場合、元の問題を分解に従って変換して得られる問題は、元の問題よりも超多項式的に大きくならない。

扱いやすい構造的制約のほとんどは分解法の幅を固定することから生じますが、他の制約も開発されています。中には分解法の観点から再定式化できるものもあります。例えば、二項非巡回問題への制約は、木幅1の問題への制約として再定式化できます。また、誘導幅（分解では定義されていない）への制約は、木クラスタリングとして再定式化できます。

初期の構造的制約（後に誘導幅に基づく制約へと発展）は、問題の主グラフの幅に基づいています。グラフのノードの順序が与えられた場合、ノードの幅は、そのノードに結合し、順序においてそのノードより前に位置するノードの数です。しかし、幅のみを制限しても扱いやすい制約にはつながりません。この幅を 4 に制限しても、充足可能性の確立はNP 完全のままです。扱いやすさは関係を制限することで得られます。特に、問題に幅があり、強く一貫性がある場合、その問題は効率的に解決可能です。これは、制約のスコープと関係の両方に依存するため、構造的でも関係的でもない制約です。 $k$ $k$

参照

グラフ理論における木分解
一般的なグラフの周辺化を抽出するために機械学習で使用されるジャンクションツリーアルゴリズム。

オンラインリソース

一般的なツリー/ハイパーツリー分解に関するオンラインリソースへのリンクをいくつか示します。

Treewidthlib : Treewidthおよび関連するグラフ問題のアルゴリズムのベンチマーク
論文「Treewidthのための完全なAnytimeアルゴリズム、Vibhav GogateとRina Dechter、UAI 2004」で使用されたC++実装。リンクは著者のホームページで、LINUXソースとWindows実行ファイルの両方が配布されています。
いくつかのヒューリスティックを使用したハイパーツリー分解の実装。
ツールバーツールには、いくつかのツリー分解ヒューリスティックが実装されています。
TreeDライブラリ:いくつかの分解方法のソースコードがあります

参考文献

デヒター、リナ(2003).制約処理. モーガン・カウフマン.ISBN 1-55860-890-7
ロッド・ダウニー、マイケル・フェローズ(1997).パラメータ化された複雑性. シュプリンガー.ISBN 0-387-94883-X
ゴットロブ, ゲオルグ;レオーネ, ニコラ; スカルチェロ, フランチェスコ (2001). 「ハイパーツリー分解：概観」 . MFCS 2001. pp. 37– 57.
ゴットロブ, ゲオルグ; レオーネ, ニコラ; スカルチェロ, フランチェスコ (2000). 「構造的CSP分解法の比較」 .人工知能. 124 (2): 243– 282. doi : 10.1016/S0004-3702(00)00078-3 .