最小シュタイナー森

むずかしい

最小シュタイナー森

無向グラフ と、その頂点の部分集合 が与えられます。 の部分グラフであって、 を全て含む森をシュタイナー森といいます。このうち、最小コストのものを最小シュタイナー森といいます。

森なので辺のないグラフを取ればよいです。

無向グラフ と頂点対の集合 が与えられます。 に含まれるどの頂点対も連結になるような の部分グラフをシュタイナー森といいます。このうち、最小コストのものを最小シュタイナー森といいます。

NP困難なので解けません。

大罪を犯してしまった・・・

— gazelle (@gzlcp) 2021年10月3日

シュタイナー木問題の一般化として知られています。

最小シュタイナー木

ところで、森ではなく木の場合もNP困難です。