将图拆分为<=N节点的断开连接的子图的算法，挑战在于获得最大数量的子图(networkx，python)

Question

我想知道是否有一种算法可以将大型图形/网络拆分为最多N个节点的多个断开连接的网络;您希望在哪里实现尽可能多的断开连接的网络？如果没有，你将如何在python/networkx中编码？

换句话说，假设我有一个由 1000 个节点组成的大型互连网络，我想删除尽可能少的节点，以便获得最多 10 个节点的子图(尽可能多的(。

Answer 1

一些坏消息：这是独立集的推广，它是NP困难的。 (独立集问题通常被框定为保留顶点的子集，但它与 n 固定为 1 的问题相同。 这意味着不太可能存在可以精确解决这个问题的多项式时间算法。