勉強会に参加したい方は概要を確認してください。

定期宣伝

弊社はエンジニアを熱烈募集しています．以下から気軽にカジュアル面談申し込んでください．就職・転職を考えている知人にも積極的に宣伝してください．

この勉強会の宣伝もお願いします．参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会で実況や感想，質問を呟くなども．

最小シュタイナー木問題

<aside> ❓

辺に正の重みのついた $N$ 頂点の無向グラフ $G$ とその頂点部分集合 $T$ （ターミナル）が与えられる。

$T$ を全て含むような $G$ の連結部分グラフであって重みが最小のものを求めよ。

</aside>

実社会の問題の帰着先としてよく出る問題で、AHC のようなマラソンコンテストでも頻出。

$T=V$ の時は最小全域木と呼ばれ、Prim法やKruskal法などの貪欲アルゴリズムが知られている。

一般の場合は辺重みなし（全ての辺重みが1）の時ですら NP-complete であり、高速に解くことは難しい。

近似解を求めるアルゴリズムもたくさん研究されているが、今回は厳密解を求める指数時間アルゴリズムを紹介する。

ターミナルの個数 $|T|$ を $k$ として $O(N3^k + (N+M)2^k \log N)\simeq O(N 3^k)$ 時間。

$G$ が木の場合は簡単で、ある種の貪欲で解くことが出来る。（ABC-D 程度）

このケースでは固定の $G$ に対してクエリとしてさまざまな $T$ がオンラインで与えられる問題も解くことが出来る。（ABC-F,G 程度）