分岐分解

グラフ理論において、無向グラフGの分岐分解は、 Gの辺の階層的クラスタリングであり、Gの辺を葉とする根なし二分木Tによって表される。 Tから任意の辺を削除すると、 Gの辺は2 つのサブグラフに分割され、分解の幅は、このようにして形成されたサブグラフの任意のペアの共有頂点の最大数になる。Gの分岐幅は、 Gの任意の分岐分解の最小幅である。

枝幅は木幅と密接に関係しています。すべてのグラフについて、これらの数値は互いに定数倍以内であり、両方の量は禁制のマイナーによって特徴付けられる場合があります。また、木幅と同様に、枝幅が小さいグラフでは多くのグラフ最適化問題が効率的に解決される場合があります。ただし、木幅とは異なり、平面グラフの枝幅は多項式時間で正確に計算される場合があります。枝分解と枝幅は、グラフからマトロイドに一般化することもできます。

根無し二分木は、閉路のない連結された無向グラフで、各非葉ノードにはちょうど 3 つの隣接ノードがあります。枝分解は、根無し二分木T と、 Tの葉と指定されたグラフG  = ( V , E )の辺との間の一対一表現で表すことができます。eが木Tの任意の辺である場合、Tからe を削除すると、 T は 2 つのサブツリーT ₁とT ₂に分割されます。このTのサブツリーへの分割により、 Tの葉に関連付けられた辺が G の 2 つのサブグラフ G 1 と G 2 に分割されます。 Gを2_つのサブグラフ_に分割することをe 分離と呼びます。

e-分離の幅は、E ₁の辺とE ₂の辺の両方に接するGの頂点の数です。つまり、2 つのサブグラフG ₁とG ₂によって共有される頂点の数です。分岐分解の幅は、その e-分離の最大幅です。Gの分岐幅は、 Gの分岐分解の最小幅です。

グラフの枝分解は木分解と密接に関連しており、枝幅は木幅と密接に関連している。2つの量は常に互いに一定の係数以内にある。特に、枝幅を導入した論文で、ニール・ロバートソンとポール・シーモア^[1]は、 木幅kと枝幅b >1のグラフGについて、

${\displaystyle b-1\leq k\leq \left\lfloor {\frac {3}{2}}b\right\rfloor -1.}$

カービング幅は、枝幅と同様に定義される概念ですが、枝が頂点に置き換えられ、その逆も同様です。カービング分解は、各葉が元のグラフの頂点を表す、根なしの二分木であり、カットの幅は、両方のサブツリーの頂点に付随する枝の数 (または重み付きグラフの合計重み) です。

分岐幅アルゴリズムは、通常、同等のカービング幅問題に還元することによって機能します。特に、平面グラフの中間グラフのカービング幅は、元のグラフの分岐幅のちょうど2倍です。^[2]

グラフGとk の両方が問題の入力とみなされる場合、グラフGが最大で幅kの分岐分解を持つかどうかを判断することはNP 完全です。 ^{[2]しかし、最大で分岐幅}kのグラフはグラフのマイナー閉族を形成し、^[3]分岐幅の計算は固定パラメータで扱いやすいことがわかります。つまり、任意の固定定数kに対して分岐幅kのグラフ上で実行時間が入力グラフのサイズに線形である、最適な分岐分解を計算するアルゴリズムが存在します。 ^[4]

平面グラフの場合、枝幅は多項式時間で正確に計算できます。これは、平面グラフの計算量がよく知られた未解決問題である木幅とは対照的です。^[5] Paul SeymourとRobin Thomasによる平面枝幅の元のアルゴリズムは、 n頂点のグラフでO( n ² ) の時間がかかり、この幅の枝分解を構築するアルゴリズムは O( n ⁴ ) の時間がかかりました。^{[2]これは後に O(} n ³ )に高速化されました。^[6]

木幅と同様に、枝幅は、入力グラフまたはマトロイドの幅に指数関数的な時間を使用して、多くのNP困難な最適化問題に対する動的計画法アルゴリズムの基礎として使用できます。 ^[7]たとえば、Cook & Seymour (2003) は、枝幅ベースの動的計画法を、巡回セールスマン問題に対する複数の部分解を単一の全体解にマージする問題に適用しました。これは、部分解の和集合からスパースグラフを形成し、スペクトルクラスタリングヒューリスティックを使用してこのグラフの適切な枝分解を見つけ、動的計画法を分解に適用することによって行われました。 Fomin & Thilikos (2006) は、平面グラフ上で固定パラメータで扱いやすいアルゴリズムを開発する場合、枝幅の方が木幅よりも適していると主張しています。その理由はいくつかあります。枝幅は木幅の境界よりも、関心のあるパラメータの関数によって厳密に制限される可能性があり、単に近似するのではなく多項式時間で正確に計算でき、計算アルゴリズムには大きな隠れた定数がありません。

グラフの分岐分解を一般化するマトロイドの分岐分解の概念を定義することも可能である。^[8]マトロイドの分岐分解は、マトロイド要素の階層的クラスタリングであり、マトロイドの要素を葉に持つ根なし二分木として表される。e分離はグラフの場合と同じ方法で定義でき、マトロイド要素の集合 M を2つの部分集合AとBに分割する。ρ がマトロイドのランク関数を表す場合、e分離の幅はρ( A ) + ρ( B ) − ρ( M ) + 1と定義され、分解の幅とマトロイドの分岐幅も同様に定義される。グラフの枝幅とそれに対応するグラフィックマトロイドの枝幅は異なる場合があります。たとえば、3辺のパスグラフと3辺のスターグラフの枝幅はそれぞれ2と1と異なりますが、どちらも枝幅1の同じグラフィックマトロイドを誘導します。^[9]ただし、木ではないグラフの場合、グラフの枝幅は、関連するグラフィックマトロイドの枝幅に等しくなります。^[10]マトロイドの枝幅はその双対マトロイドの枝幅に等しく、特にこれは木ではない平面グラフの枝幅がその双対の枝幅に等しいことを意味します。^[9]

枝幅は、グラフマイナーの理論をマトロイドマイナーに拡張する試みの重要な要素です。木幅はマトロイドにも一般化でき、^[11]グラフマイナーの理論では枝幅よりも大きな役割を果たしますが、マトロイドの設定では枝幅の方が便利な特性を持っています。^{[12]ロバートソンとシーモアは、グラフの}ロバートソン-シーモア定理と同様に、特定の有限体上で表現可能なマトロイドは準整列していると推測しましたが、これまでのところ、これは枝幅が制限されたマトロイドに対してのみ証明されています。^[13]さらに、有限体上で表現可能なマトロイドのマイナー閉族にすべての平面グラフのグラフィックマトロイドが含まれていない場合、族内のマトロイドの枝幅には定数の境界があり、マイナー閉グラフ族に対して同様の結果を一般化します。^[14]

任意の固定定数kに対して、最大でkの枝幅を持つマトロイドは、独立オラクルを介してマトロイドにアクセスできるアルゴリズムによって多項式時間で認識できる。^[15]

ロバートソン・シーモア定理により、枝幅kのグラフは禁制マイナーの有限集合によって特徴付けられる。枝幅 0 のグラフはマッチングであり、最小の禁制マイナーは 2 辺パスグラフと三角形グラフ (または、単純グラフではなくマルチグラフを考慮する場合は 2 辺サイクル) である。^{[16]枝幅 1 のグラフは、各}連結コンポーネントがスターであるグラフであり、枝幅 1 の最小の禁制マイナーは三角形グラフ (または、単純グラフではなくマルチグラフを考慮する場合は 2 辺サイクル) と 3 辺パスグラフである。^[16]枝幅 2 のグラフは、各 2連結コンポーネントが直列並列グラフであるグラフであり、唯一の最小の禁制マイナーは4 つの頂点を持つ完全グラフ K ₄である。^[16]グラフの枝幅が3であるためには、木幅が3で、立方体グラフをマイナーグラフとして持たない必要がある。したがって、4つの極小禁制マイナーグラフは、木幅3の4つの禁制マイナーグラフのうちの3つ（八面体のグラフ、完全グラフK ₅、およびワグナーグラフ）と、立方体グラフを合わせたものである。^[17]

禁制マイナーは、この場合ロバートソン・シーモア定理に完全に類似するものがないにもかかわらず、マトロイドの枝幅についても研究されてきた。マトロイドの枝幅が 1 になるのは、すべての要素がループまたはコロループである場合のみであり、したがって、唯一の最小禁制マイナーは、三角形グラフのグラフィックマトロイドであるユニフォームマトロイドU(2,3) である。マトロイドの枝幅が 2 になるのは、枝幅が 2 のグラフのグラフィックマトロイドである場合のみであり、したがって、その最小禁制マイナーは、K ₄のグラフィックマトロイドと非グラフィックマトロイド U(2,4) である。枝幅が 3 のマトロイドは、有限体上の表現可能性という追加の仮定がなければ、十分に準順序付けされていないが、それでも、枝幅に有限の境界を持つマトロイドには、枝幅の指数関数以下の要素数を持つ、有限個の最小禁制マイナーがある。^[18]

ウィキメディア・コモンズには、ツリー分解に関連するメディアがあります。