k最小全域木

理論計算機科学で研究されている 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) は、各端末に、木あたりt個の大きな頂点を持つ重みゼロのエッジの木を添付しました。( n個の頂点とr 個の端末を持つグラフの場合、木あたり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]

• 「NP最適化問題大要」の最小k-スパニングツリー
• KCTLIB、KCTLIB - エッジ重み付き K カーディナリティ ツリー問題用のライブラリ