シュタイナー木の問題

組み合わせ数学において、ヤコブ・シュタイナーにちなんで名付けられたシュタイナー木問題、または最小シュタイナー木問題は、組み合わせ最適化における一連の問題の総称です。シュタイナー木問題はさまざまな設定で定式化できますが、いずれも与えられたオブジェクトの集合と事前に定義された目的関数に対して最適な相互接続を必要とします。シュタイナー木問題という用語と同義語としてよく使われる有名な変種の一つに、グラフにおけるシュタイナー木問題があります。非負のエッジ重みと、通常は終端と呼ばれる頂点のサブセットを持つ無向グラフが与えられた場合、グラフにおけるシュタイナー木問題では、すべての終端を含み（ただし、追加の頂点を含む場合もある）、エッジの総重みを最小化する最小重みの木を求めます。さらに有名な変種としては、ユークリッドシュタイナー木問題と直線最小シュタイナー木問題があります。

グラフにおけるシュタイナー木問題は、他の2つの有名な組み合わせ最適化問題、すなわち（非負）最短経路問題と最小全域木問題の一般化と見なすことができます。グラフにおけるシュタイナー木問題にちょうど2つの終端点がある場合、それは最短経路を見つける問題に帰着します。一方、すべての頂点が終端点である場合、グラフにおけるシュタイナー木問題は最小全域木問題と同等です。しかし、非負最短経路問題と最小全域木問題はどちらも多項式時間で解くことができますが、シュタイナー木問題にはそのような解法は知られていません。与えられた入力に対して、ある閾値よりも重みの小さい木が存在するかどうかを問う決定版はNP完全であり、これは、与えられたグラフにおける最小重み木を求める最適化版がNP困難であることを意味します。実際、決定版はKarpが最初に挙げた21個のNP完全問題の中に含まれていました。グラフにおけるシュタイナー木問題は、回路レイアウトやネットワーク設計に応用される。しかし、実際の応用では通常、様々なバリエーションが必要となるため、シュタイナー木問題には数多くの変種が存在する。

シュタイナー木問題のほとんどのバージョンはNP困難ですが、いくつかの制限されたケースは多項式時間で解くことができます。悲観的な最悪のケースの複雑さにもかかわらず、グラフ内のシュタイナー木問題や直線シュタイナー木問題など、いくつかのシュタイナー木問題の変種は、大規模な現実世界の問題であっても、実際には効率的に解くことができます。^{[ 1 ] [ 2 ]}

元の問題は、ユークリッド・シュタイナー木問題または幾何学的シュタイナー木問題として知られるようになった形式で記述されました。平面上のN個の点が与えられたとき、任意の 2 つの点が直接または他の点と線分を介して線分で相互接続されるように、合計の長さが最小となる線でそれらを接続することが目標です。

この問題はシュタイナーにちなんで名付けられていますが、最初に提起したのは1811年にジョセフ・ディエ・ジェルゴンヌによって次の形で提起されました。「平面上に既知の位置に複数の都市があり、それらの都市を総延長が可能な限り短い運河システムで結ぶことが問題である」^{[ 3 ] 。}

接続する線分は、端点以外では互いに交差せず、木構造を形成することが示される。これがこの問題の名前の由来である。

N  =  3の問題は長い間検討されてきましたが、すぐに、与えられたN個の点すべてに接続する単一のハブを持つ、総長が最小のスター ネットワークを見つける問題に拡張されました。しかし、完全なシュタイナー木の問題はガウスの手紙で定式化されましたが、その最初の本格的な扱いは、1934 年にVojtěch JarníkとMiloš Kösslerによってチェコ語で書かれた論文でした。この論文は長い間見過ごされていましたが、すでに「シュタイナー木のほぼすべての一般的な性質」が含まれており、後に他の研究者に帰属され、平面から高次元への問題の一般化も含まれています。^{[ 4 ]}

ユークリッドシュタイナー問題では、グラフに追加される点（シュタイナー点）は次数が3でなければならず、そのような点に接続する3つの辺は3つの120度の角を形成しなければならない（フェルマー点を参照）。したがって、シュタイナー木が持つことができるシュタイナー点の最大数はN - 2  である。ここでNは最初に与えられた点の数である。（これらの性質はすべてゲルゴンヌによって既に確立されている。）

N = 3の場合、2 つのケースが考えられます。与えられた点によって形成される三角形のすべての角度が 120 度未満である場合、解はフェルマー点に位置するシュタイナー点によって与えられます。そうでない場合、解は 120 度以上の角度で交わる三角形の 2 辺によって与えられます。

一般のNに対して、ユークリッド シュタイナー木問題はNP 困難であるため、多項式時間アルゴリズムを使用して最適解を見つけることができるかどうかはわかりません。ただし、ユークリッド シュタイナー木には多項式時間近似スキーム(PTAS)があり、つまり、ほぼ最適な解を多項式時間で見つけることができます。^{[ 5 ]}複雑性クラス NP への所属が不明であるため、ユークリッド シュタイナー木問題が NP 完全であるかどうかはわかりません。

直線シュタイナー木問題は、平面上の幾何学的シュタイナー木問題の変形であり、ユークリッド距離が直線距離に置き換えられています。この問題は、電子設計自動化の物理設計で発生します。VLSI回路では、配線は設計規則によって垂直方向と水平方向にのみ走るように制約されることが多い配線によって行われるため、直線シュタイナー木問題は、2つ以上の端子を持つネットの配線をモデル化するために使用できます。^{[ 6 ]}

シュタイナー木は、重み付きグラフの文脈で広く研究されてきました。その原型は、おそらくグラフにおけるシュタイナー木問題でしょ う。G = ( V , E )を非負のエッジ重み c を持つ無向グラフとし、S ⊆ V を終端と呼ばれる頂点の部分集合とします。シュタイナー木は、 Sを張るG内の木です。この問題には 2 つのバージョンがあります。シュタイナー木に関連する最適化問題では、タスクは最小重みのシュタイナー木を見つけることです。決定問題では、エッジ重みは整数であり、タスクは総重みが事前に定義された自然数kを超えないシュタイナー木が存在するかどうかを判定することです。決定問題は、 Karp の 21 個の NP 完全問題の 1 つです。したがって、最適化問題はNP 困難です。グラフにおけるシュタイナー木問題は、マルチキャストルーティング^{[ 8 ]}やバイオインフォマティクスなど、研究や産業のさまざまな問題に適用されています^{[ 7 ]}。^{[ 9 ]}     

この問題の特殊なケースは、Gが完全グラフであり、各頂点v  ∈ V が 距離空間内の点に対応し、各e ∈ Eの辺の重みw ( e )が空間内の距離に対応する場合である。言い換えれば、辺の重みは三角不等式を満たす。この変種は、距離シュタイナー木問題として知られている。非距離シュタイナー木問題のインスタンスが与えられた場合、それを多項式時間で同等の距離シュタイナー木問題のインスタンスに変換することができる。この変換は近似係数を保持する。^{[ 10 ]}  

ユークリッド版ではPTASが認められるが、メトリックシュタイナー木問題はAPX完全であることが知られている。つまり、P = NPでない限り、多項式時間で1に任意に近づく近似比を達成することは不可能である。最小シュタイナー木を係数の範囲内で近似する多項式時間アルゴリズムが存在する。${\displaystyle \ln(4)+\varepsilon \approx 1.386}$[ ^{11 ]} ただし、係数の範囲内で近似する^と${\displaystyle 96/95\approx 1.0105}$NP困難である。^{[ 12 ]}距離が1と2のシュタイナー木問題の制限されたケースについては、1.25近似アルゴリズムが知られている。^{[ 13 ]}カルピンスキーとアレクサンダー・ゼリコフスキーは、シュタイナー木問題の密なインスタンスに対してPTASを構築した。^{[ 14 ]}

グラフ問題の特殊なケースである準二部グラフのシュタイナー木問題では、SはGのすべてのエッジの少なくとも 1 つの端点を含む必要があります。

シュタイナー木問題は、より高次元およびさまざまな曲面でも研究されてきました。球面、トーラス、射影平面、広円錐、狭円錐などにおいて、シュタイナー最小木を見つけるアルゴリズムが見つかっています。^{[ 15 ]}

シュタイナー木問題のその他の一般化としては、kエッジ連結シュタイナーネットワーク問題とk頂点連結シュタイナーネットワーク問題があり、その目的は連結グラフではなく、 kエッジ連結グラフまたはk頂点連結グラフを見つけることです。さらによく研究されている^{[ 16 ]}一般化として、生存可能なネットワーク設計問題 (SNDP)があり、そのタスクは、各頂点ペアを、指定された数 (0 の場合もある) のエッジまたは頂点が互いに素なパスで接続することです。

シュタイナー問題は、距離空間の一般的な設定や、無限に多くの点の場合にも定式化されている。^{[ 17 ]}

一般的なグラフシュタイナー木問題は、終端頂点によって誘導されるグラフのメトリック閉包の部分グラフの最小全域木を計算することによって近似できる。これは、1981年にKouらによって初めて発表された^{[ 18 ]。}グラフのメトリック閉包${\displaystyle G}$は、各エッジがノード間の最短経路距離で重み付けされた完全グラフです。${\displaystyle G}$このアルゴリズムは、重みが${\displaystyle 2-2/t}$最適シュタイナー木の重みの係数${\displaystyle t}$は最適シュタイナー木の葉の数です。これは、最適シュタイナー木上の巡回セールスマンのツアーを考えることで証明できます。この近似解は で計算できます。${\displaystyle O(|S||V|^{2})}$多項式時間で、まず全ペア最短経路問題を解いてメトリック閉包を計算し、次に最小全域木問題を解くことによって実現します。

グラフにおけるシュタイナー木を近似する別の一般的なアルゴリズムは、1980年に高橋と松山によって発表された。^{[ 19 ]}彼らの解法は、任意の頂点から始めて、木から最も近い頂点への最短経路を繰り返し追加することによって、シュタイナー木を段階的に構築する。${\displaystyle S}$まだ追加されていないもの。このアルゴリズムには${\displaystyle O(|S||V|^{2})}$実行時間、そして重量が${\displaystyle 2-2/|S|}$最適な。

1986年、Wuら^{[ 20 ]}は、全ペア最短経路の事前計算を回避することで実行時間を劇的に改善した。代わりに、最小全域木を計算するためにKruskalのアルゴリズムと同様のアプローチを採用し、森から開始した。${\displaystyle |S|}$互いに素な木を複数作成し、ダイクストラ法に似た幅優先探索を用いて、複数の初期頂点から同時に「成長」させます。探索中に現在の木に属さない頂点に遭遇すると、2つの木が1つにマージされます。このプロセスは、1つの木だけが残るまで繰り返されます。優先度キューを実装するためにヒープ（データ構造）を使用し、訪問した各頂点がどの木に属するかを追跡するために互いに素な集合のデータ構造を使用することで、このアルゴリズムは、${\displaystyle O(|E|\log |V|)}$実行時間は改善されませんが、${\displaystyle 2-2/t}$Kouらによるコスト比率

一連の論文では、最小シュタイナー木問題に対する近似アルゴリズムが提供され、その近似比は${\displaystyle 2-2/t}$比率。この一連の研究は、最小コスト終端全域木を反復的に改善することで比率を 1.55 に改善した Robins と Zelikovsky の 2000 年のアルゴリズムで頂点に達した。^{[ 21 ]}しかし、より最近では、Byrka らは、${\displaystyle \ln(4)+\varepsilon \leq 1.39}$線形計画緩和と反復ランダム化丸めと呼ばれる手法を用いた近似。^{[ 11 ]}

一般グラフシュタイナー木問題は、ドレイファス・ワグナーアルゴリズムによって、終端の数をパラメータとして固定パラメータ扱い可能であることが知られています。 ^{[ 22 ] [ 23 ]}ドレイファス・ワグナーアルゴリズムの実行時間は${\displaystyle 3^{|S|}{\text{poly}}(n)}$ここで、nはグラフの頂点の数、Sは終端点の集合である。より高速なアルゴリズムも存在し、${\displaystyle c^{|S|}{\text{poly}}(n)}$どんな時間でも${\displaystyle c>2}$または、小さな重量の場合は、${\displaystyle 2^{|S|}{\text{poly}}(n)W}$時間、ここでWは任意のエッジの最大重みです。^{[ 24 ] [ 25 ]}上記のアルゴリズムの欠点は、指数空間を使用することです。多項式空間で実行されるアルゴリズムも存在します。${\displaystyle 2^{|S|}{\text{poly}}(n)W}$時間と${\displaystyle (7.97)^{|S|}{\text{poly}}(n)\log W}$時間。^{[ 26 ] [ 27 ]}

一般グラフシュタイナー木問題には、実行可能なパラメータ付きアルゴリズムが存在しないことが知られています。${\displaystyle 2^{\epsilon t}{\text{poly}}(n)}$どんな時間でも${\displaystyle \epsilon <1}$ここで、tは最適なシュタイナー木の辺の数である。ただし、集合被覆問題にアルゴリズムが実装されている場合は除く。${\displaystyle 2^{\epsilon n}{\text{poly}}(m)}$少し時間${\displaystyle \epsilon <1}$ここで、nとmはそれぞれ集合被覆問題のインスタンスの要素数と集合数である。^{[ 28 ]}さらに、この問題は、以下の条件を満たさない限り、多項式カーネルを許容しないことが知られている。${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$最適シュタイナー木の辺の数によってパラメータ化され、すべての辺の重みが 1 の場合でも同様である。^{[ 29 ]}

グラフシュタイナー木問題は、以下の条件を満たさない限り多項式カーネルを許容しない。${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$端末数によってパラメータ化され、多項式サイズの近似カーネル化スキーム（PSAKS）が許容される。任意の${\displaystyle \varepsilon >0}$多項式サイズのカーネルを計算することは可能であり、${\displaystyle 1+\varepsilon }$溶液の品質に影響を与える。^{[ 30 ]}

グラフシュタイナー木問題を最適解における非終端点（シュタイナー頂点）の数pでパラメータ化すると、この問題はW[1] 困難になります（前述の終端点の数によるパラメータ化とは対照的です）。同時に、この問題はAPX 完全であり、P = NPでない限りPTAS は存在しません。しかし、任意の p に対してパラメータ化された近似スキームが存在します。${\displaystyle \varepsilon >0}$を計算する${\displaystyle (1+\varepsilon )}$-近似${\displaystyle 2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}}$時間。^{[ 31 ]}また、このパラメータ化のためのPSAKSも存在します。^{[ 31 ]}

シュタイナー比は、ユークリッド平面上の点の集合に対する最小全域木と最小シュタイナー木の全長比の上限である。 ^{[ 32 ]}

ユークリッドシュタイナー木問題において、ギルバート・ポラック予想はシュタイナー比が${\displaystyle {\tfrac {2}{\sqrt {3}}}\approx 1.1547}$、正三角形の 3 つの点と、三角形の 2 辺を使用する全域木、および三角形の重心を通して点を結ぶシュタイナー木によって達成される比率。以前に証明が主張されたにもかかわらず、 ^{[ 33 ]}この予想はまだ未解決です。^{[ 34 ]}この問題に対する最も広く受け入れられている上限は、 ChungとGraham (1985)による 1.2134 です。

直線シュタイナー木問題の場合、シュタイナー比は正確に${\displaystyle {\tfrac {3}{2}}}$、正方形内の4つの点と、正方形の3辺を使用する全域木、および正方形の中心を通る点を結ぶシュタイナー木によって達成される比率。^{[ 35 ]}より正確には、${\displaystyle L_{1}}$正方形を傾ける距離${\displaystyle 45^{\circ }}$座標軸に関して、一方${\displaystyle L_{\infty }}$正方形の距離は、軸に沿って配置されるべきです。

• 不透明な森林問題
• 巡回セールスマン問題
• ウィーナーコネクタ

• GeoSteiner（ユークリッド空間および直線空間におけるシュタイナー木問題を解くためのソフトウェア。ソースコードは公開されており、非商用利用は無料）
• SCIP-Jack（グラフにおけるシュタイナー木問題および14種類の変形問題（例：賞金収集型シュタイナー木問題）を解くためのソフトウェア。非商用利用は無料）
• 三角形のシュタイナー頂点（すなわちフェルマー点）、三角形の頂点からの距離、および相対的な頂点の重みを求めるためのFortranサブルーチン。
• Phylomurka（グラフにおける小規模シュタイナー木問題のソルバー）
• https://www.youtube.com/watch?v=PI6rAOWu-Og (動画：水と石鹸でシュタイナーの木の問題を解決する)
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017)、「シュタイナー木を用いたバルクデータ転送の平均完了時間の最小化」、DCCast: データセンター間における効率的なポイントツーマルチポイント転送、USENIX Association、arXiv : 1707.02096
• ハゼウィンケル、M. (2001) [1994]、「シュタイナー木問題」、数学百科事典、EMS Press
• M. Hauptmann、M. Karpinski (2013): シュタイナー木問題の概要