graph-theory - グラフの切断されたコンポーネントを結合する頂点の最小数を見つける方法は?

Question

固定数のノードとエッジを持つグラフがあるとします。ただし、すべてのノードが常にアクティブであるとは限らないため、グラフが切断されます。この種の状況では、アクティブなままの場合にグラフを常に接続したままにする頂点の最小セットを見つけたいと思います。

どうすればこの問題を解決できますか? この問題は既知の問題にマッピングできますか?

Answer 1

これは、Connected Dominating Set のように聞こえます。