シュタイナー木問題

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

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

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

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

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

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

N  = 3の問題は長い間検討され、すぐに、N 個の与えられたポイントすべてに接続する単一のハブを持つ、全長が最小のスター ネットワークを見つける問題に拡張されました。ただし、完全なシュタイナー ツリー問題はガウスの書簡で定式化されましたが、その最初の本格的な扱いは、1934 年にチェコ語でVojtěch Jarníkと Miloš Kössler  [cs]によって書かれた論文でした。この論文は長い間見過ごされていましたが、平面から高次元への問題の一般化など、後に他の研究者に帰せられる「シュタイナー ツリーのほぼすべての一般的な特性」がすでに含まれています。^[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]やバイオインフォマティクス[9] など、研究や産業のさまざまな問題に適用されている。 ^{[ 7 ]}

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

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

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

シュタイナー木問題は、高次元や様々な表面上でも研究されてきた。球面、トーラス、射影平面、広い円錐や狭い円錐など上でシュタイナー極小木を見つけるアルゴリズムが見つかっている。^[15]

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

シュタイナー問題は、距離空間の一般的な設定や、おそらくは無限個の点に対しても述べられている。^[17]

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

グラフのシュタイナー木を近似する別の一般的なアルゴリズムは、1980年に高橋と松山によって発表されました。 ^[19]彼らのソリューションは、任意の頂点から始めて、木からS内のまだ追加されていない最も近い頂点までの最短パスを繰り返し追加することで、シュタイナー木を段階的に構築します。このアルゴリズムも実行時間がO(| S | | V |²)で、重みが最適値の2 − 2/| S |以内の木を生成します。

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

一連の論文では、最小シュタイナー木問題の近似アルゴリズムが提供され、近似比は2 − 2/ t比よりも改善されました。この一連の論文は、最小コストのターミナルスパニングツリーを反復的に改善することで比を 1.55 に改善した 2000 年の Robins と Zelikovsky のアルゴリズムで最高潮に達しました。しかし、最近では、Byrka らが線形計画緩和と反復ランダム丸めと呼ばれる手法を使用して近似を証明しました。^[11]${\displaystyle \ln(4)+\varepsilon \leq 1.39}$

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

一般的なグラフ シュタイナー木問題には、任意の （tは最適シュタイナー木の辺の数）に対して 100 分以内に実行されるパラメータ化されたアルゴリズムが存在しないことが知られています。ただし、集合被覆問題には、ある （n と m はそれぞれ集合被覆問題のインスタンスの要素数と集合数）に対して 100 分以内に実行されるアルゴリズムが存在します。 [ 27 ]さらに、 （最適シュタイナー木の辺の数でパラメータ化されていても、すべての辺の^重みが 1 の場合）でない限り、この問題は多項式カーネルを許容しないことが知られています。^[28]${\displaystyle 2^{\epsilon t}{\text{poly}}(n)}$${\displaystyle \epsilon <1}$${\displaystyle 2^{\epsilon n}{\text{poly}}(m)}$${\displaystyle \epsilon <1}$${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$

グラフシュタイナー木問題は、端末の数でパラメータ化されない限り多項式カーネルを許容しないが、多項式サイズの近似カーネル化スキーム（PSAKS）を許容する。任意のグラフに対して、多項式サイズのカーネルを計算することが可能であり、解の品質が1要素だけ低下する。^[29]${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$${\displaystyle \epsilon >0}$${\displaystyle 1+\varepsilon }$

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

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

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

直線シュタイナー木問題の場合、シュタイナー比はちょうど であり、これは正方形の3辺を使用する全域木と、正方形の中心を通って点を結ぶシュタイナー木を持つ正方形内の4つの点によって達成される比である。^[34]より正確には、距離の場合、正方形は座標軸に対して だけ傾けられるべきであり、距離の場合、正方形は軸に沿っているべきである。 ${\displaystyle {\tfrac {3}{2}}}$${\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)、「Steiner Trees を使用してバルク データ転送の平均完了時間を最小化する」、DCCast: データセンター間の効率的なポイントツーマルチポイント転送、USENIX Association、arXiv : 1707.02096
• Hazewinkel, M. (2001) [1994]、「シュタイナー木問題」、数学百科事典、EMS Press
• M. ハウプトマン、M. カルピンスキー (2013): シュタイナーツリー問題集