12

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

(*) 我明白，在一般情况下，任何此类算法都可能具有 O(2^n) 复杂度，因为对于一个集团 (Kn)，有 2^n 个连接子图。但是，我通常处理的图的连接子图要少得多，所以我正在寻找一种方法来生成它们，而不必考虑所有 2^n 子图并丢弃那些未连接的子图（如这个问题的解决方案）。

运行时间与解的数量呈线性关系的算法（即，它可以直接从图的结构中生成解，而不会浪费时间考虑所有非解）显然是理想的。节点数量的多项式的附加步骤也可以（例如，预先计算图的传递闭包 - 我认为这在这种情况下会有所帮助）。

或者，证明没有这样的解决方案至少会让我摆脱痛苦。

4

1 回答 1

11

在递归伪代码中，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))

编辑：对于最大度数 O(1) 的图，我们可以通过保持 来实现真正的线性时间，verticesNotYetConsidered intersect neighbors为了清楚起见，我没有这样做。如果您通过将图形表示为邻接矩阵，其中每一行存储为一个或两个字位图来利用字并行性，这种优化可能并不值得。

于 2013-03-27T13:02:26.550 回答