Loading article…
理論計算機科学で研究されているk最小全域木問題は、頂点数がちょうどk個で、より大きなグラフの部分グラフを形成する最小コストの木を求める問題です。これはk -MSTまたはエッジ重み付きkカーディナリティ木とも呼ばれます。この木を見つけることはNP困難ですが、定数近似比の範囲内で多項式時間で近似することができます。
この問題への入力は、エッジに重みが付けられた無向グラフと数kです。出力はk 個の頂点とk − 1 個のエッジを持つ木で、出力木のすべてのエッジは入力グラフに属します。出力のコストはエッジの重みの合計であり、目標は最小コストの木を見つけることです。この問題はLozovanu & Zelikovsky (1993) [ 1 ]およびRavi et al. (1996)によって定式化されました。
Ravi らは、この問題の幾何学的バージョンも検討しており、これはグラフ問題の特殊なケースと見なすことができる。幾何学的k最小全域木問題では、入力は平面上の点の集合である。ここでも、出力は、k個の点を頂点とする木であり、その辺のユークリッド長の合計を最小化する必要がある。つまり、これは、ユークリッド距離を重みとする完全グラフ上のグラフk最小全域木である。 [ 2 ]
kが固定定数の場合、 k最小全域木問題は、すべてのk組の頂点を試す総当たり探索アルゴリズムによって多項式時間で解くことができます。しかし、変数kの場合、k最小全域木問題は、シュタイナー木問題からの還元によってNP 困難であることが示されています。[ 1 ] [ 2 ]
この還元法は、入力としてシュタイナー木問題のインスタンス、すなわち、頂点のサブセットが終端として選択された重み付きグラフを受け取ります。シュタイナー木問題の目標は、これらの終端を、重みが可能な限り小さい木で接続することです。この問題をk最小全域木問題のインスタンスに変換するために、Ravi ら (1996) は、各終端に、1 本の頂点の数tが大きい、重みがゼロのエッジの木を付加します。( n個の頂点とr個の終端を持つグラフの場合、 1 本の頂点ごとにt = n − r − 1 個の頂点を追加します。) 次に、 k = rtのこの拡張グラフでk最小全域木を求めます。k 全域木にこれほど多くの頂点を含める唯一の方法は、追加された各木から少なくとも 1 つの頂点を使用することです。追加された木のうち 1 つでも欠けると、残りの頂点が足りなくなるためです。しかし、この kの選択では、 k全域木には、すべての終端を接続するために必要なだけの元のグラフのエッジのみが含まれる可能性があります。したがって、 k最小全域木は、最適なシュタイナー木と、追加された木の重みゼロのエッジを十分に組み合わせて、木全体のサイズを十分に大きくすることによって形成する必要があります。[ 2 ]
エッジの重みが集合{1, 2, 3 }に属するグラフであっても、最適解の値が与えられた閾値より小さいかどうかをテストすることはNP 完全です。平面グラフの場合も NP 完全です。この問題の幾何学的バージョンも NP 困難ですが、平方根の和を比較するのが難しいため NP に属することは知られていません。代わりに、実数の存在理論に還元できる問題のクラスに属します。[ 2 ]
k最小全域木は、木幅が制限されたグラフ、および2つの異なるエッジ重みのみを持つグラフの場合、多項式時間で見つけることができます。 [ 2 ]
k最小全域木の最適解を見つけるには計算複雑度が高いため、この問題に関する研究の多くは、代わりにこの問題の近似アルゴリズムに集中しています。このようなアルゴリズムの目標は、近似比が小さい多項式時間で近似解を見つけることです。近似比は、計算された解の長さと、この比を最大化する最悪の場合のインスタンスの最適長さの比として定義されます。k 最小全域木問題の NP 困難性削減はすべての解の重みを保持するため、問題の近似の困難性も保持します。特に、シュタイナー木問題は96/95 より優れた近似比に近似するのが NP 困難であるため、[ 3 ] k最小全域木問題についても同様です。
一般的な問題に対する既知の最良の近似は、近似比が 2 であり、Garg (2005)によるものです。[ 4 ]この近似は、 Goemans & Williamson (1992)の主双対スキームに大きく依存しています。[ 5 ] 入力がユークリッド平面上の点(任意の 2 つの点を距離に等しいコストで木に接続できる)で構成されている場合、 Arora (1998)によって考案された多項式時間近似スキームが存在します。[ 6 ]
