algorithm - 在图中查找所有关键节点集

Question

给定一个图，我想找到节点集 S1, S2, ... 的移除可能会断开网络。这些集合中的每一个都可能包含一个或多个节点。此外，这些集合中的任何一个都不是彼此的子集，即我们不考虑 S3=S1 U S2 尽管它也断开了网络。

我们不想找到：

1. 只有一个关键节点集，但所有
2. 最大程度断开网络的单组节点。

任何关于这些的任何建议：

1. 问题的难度
2. 解决方案的一些方向/论文参考
3. 我可能需要提供的任何证明

Answer 1

删除断开图的顶点集称为分隔符。参见例如 A. Berry, JP Bordat, O. Cogis：Generating all the Minimal Separators of a Graph。

Answer 2

您要查找的是图形分区。
这是一个NP难题。有关图分区的更多理解，
请参阅此内容。如果你用谷歌搜索的话，有可用的图分区的近线性时间算法。