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

Question

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

(*)我理解,在一般情况下,任何这样的算法可能具有O(2 ^ n)复杂度,因为对于clique(Kn),存在2 ^ n个连接的子图.但是,我通常处理的图形将会有更少的连接子图,所以我正在寻找一种生成它们的方法,而不必考虑所有2 ^ n个子图并扔掉那些没有连接的子图(如解决这个问题).

一种算法的运行时间与解决方案的数量成线性关系(即,它可以直接从图的结构生成解决方案而不会浪费时间考虑所有非解决方案)显然是理想的.一个额外的步骤,即节点数量的多项式也可以(例如预先计算图的传递闭包 - 不是我认为在这种情况下会有所帮助).

或者,证明没有这样的解决方案至少会让我摆脱困境.

Answer 1

在递归伪代码中,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,这是为了清晰起见我没有做的.如果通过将图表表示为邻接矩阵来利用单词并行性,其中每行存储为单字或双字位图,则此优化可能不值得.