有效地找到所有连通的诱导子图

Z时代
2024-01-10
分类：问答

是否有一种高效的（*）算法来查找连接的无向顶点标记图的所有连接的（诱导的）子图？

（*）我理解，在一般情况下，任何这样的算法都可能具有O（2 ^ n）复杂度，因为对于集团（Kn），存在2 ^n个相连的子图。但是，我通常处理的图将具有更少的连接子图，因此我正在寻找一种生成它们的方法，而不必考虑所有2 ^n个子图并丢弃那些未连接的子图

一种运行时间与解数成线性关系的算法（即，它可以直接从图的结构生成解而无需浪费时间考虑所有非解）的算法显然是理想的。在节点数量上采用多项式的附加步骤也可以（例如，预先计算图的传递闭包-

在这种情况下，我认为这样做没有帮助）。

另外，如果没有这样一种解决方案的证明，至少会使我摆脱痛苦。

回答：

在递归伪代码中，2 ^ n算法为

GenerateAndTest(verticesNotYetConsidered, subsetSoFar):
    if verticesNotYetConsidered is empty:
        yield subsetSoFar if it induces a connected subgraph
    else:
        choose a vertex v in verticesNotYetConsidered
        GenerateAndTest(verticesNotYetConsidered - {v}, subsetSoFar)
        GenerateAndTest(verticesNotYetConsidered - {v}, subsetSoFar union {v})

选择哪个顶点v无关紧要；我们甚至可以在两个同级通话中选择不同的选项。通过修剪递归树，我们利用这种自由来获得近似线性时间的算法（解数的n倍）。

如果subsetSoFar为空，则选择仍然不受限制。否则，我们选择v与中的一个顶点相邻subsetSoFar。如果不v存在这种情况，我们将屈服subsetSoFar并返回，因为此子树中没有其他解决方案。

请注意subsetSoFar始终保持连接的新不变式，因此我们可以消除显式连接性测试。我们在递归树的每个节点上执行O（n）工作（天真的O（n ^

2），但是我们可以递增地维护相邻顶点的集合），它是完全二元的，并且每个叶子的叶子都给出一个唯一的解，因此总和按照要求进行工作（回想一下，内部节点的数量比叶子的数量少一）。

由于存在新的不变性，因此不会产生任何断开的子图。

产生每个连接的子图。对于诱发连接子图的一组顶点S，遵循与S一致的分支。S的适当子集与S的其余部分不相邻是不可能的，因此S不会被修剪。

新的伪代码如下。N(v)表示的邻居集v。

GenerateConnectedSubgraphs(verticesNotYetConsidered, subsetSoFar, neighbors):
    if subsetSoFar is empty:
        let candidates = verticesNotYetConsidered
    else
        let candidates = verticesNotYetConsidered intersect neighbors
    if candidates is empty:
        yield subsetSoFar
    else:
        choose a vertex v from candidates
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar,
                                   neighbors)
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar union {v},
                                   neighbors union N(v))