有效地找到所有连接的诱导子图 [英] Efficiently find all connected induced subgraphs

问题描述

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

Is there an efficient(*) algorithm to find all the connected (induced) subgraphs of a connected undirected vertex-labelled graph?

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

(*) I appreciate that, in the general case, any such algorithm may have O(2^n) complexity because, for a clique (Kn), there are 2^n connected subgraphs. However, the graphs I'm typically dealing with will have far fewer connected subgraphs, so I'm looking for a way to generate them without having to consider all 2^n subgraphs and throw away those that aren't connected (as in the solution to this question).

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

An algorithm that has running time that's linear in the number of the solutions (i.e. it can generate the solutions directly from the structure of the graph without wasting time considering all the non-solutions) would obviously be ideal. An additional step that's polynomial in the number of nodes would be fine too (e.g. pre-computing the transitive closure of the graph - not that I think that would help in this case).

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

Alternatively, a proof that there is no such solution would at least put me out of my misery.

推荐答案

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

In recursive pseudocode, the 2^n algorithm is

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 倍于解数).

It doesn't matter which vertex v is chosen; we even can choose differently in two sibling calls. We exploit this freedom to obtain an almost linear-time algorithm (n times the number of solutions) by pruning the recursion tree.

如果 subsetSoFar 为空，则选择仍然不受约束.否则，我们选择 v 与 subsetSoFar 中的顶点之一相邻.如果不存在这样的 v，我们产生 subsetSoFar 并返回，因为在这个子树中没有其他解决方案.

If subsetSoFar is empty, then the choice is still unconstrained. Otherwise, we choose v to be adjacent to one of the vertices in subsetSoFar. If no such v exists, we yield subsetSoFar and return, since there are no other solutions in this subtree.

注意 subsetSoFar 总是连接的新不变量，因此我们可以消除显式连接测试.我们在递归树的每个节点上做 O(n) 的工作(简单的 O(n^2) 但我们可以增量地维护相邻顶点的集合)，这是完全二元的并且每个叶子都产生一个解决方案，所以总工作正如声称的那样(回想一下，内部节点的数量比叶子的数量少 1).

Note the new invariant that subsetSoFar is always connected, so we can eliminate the explicit connectivity test. We do O(n) work at each node of the recursion tree (naively O(n^2) but we can maintain the set of adjacent vertices incrementally), which is complete binary and whose leaves each yield exactly one solution, so the total work is as claimed (recall that the number of internal nodes is one less than the number of leaves).

由于新的不变量，没有产生断开的子图.

On account of the new invariant, no disconnected subgraph is yielded.

生成每个连接的子图.对于诱导连通子图的一组顶点 S，遵循与 S 一致的分支.S 的真子集不可能与 S 的其余部分不相邻，因此 S 不被剪枝.

Each connected subgraph is yielded. For a set of vertices S that induces a connected subgraph, follow the branches that agree with S. It's not possible for a proper subset of S to have no adjacency to the rest of S, so S is not pruned.

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

The new pseudocode is as follows. N(v) denotes the set of neighbors of 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 相交邻居 来实现真正的线性时间，为了清楚起见，我没有这样做.如果您通过将图表示为邻接矩阵(其中每一行存储为一个或两个字的位图)来利用词并行性，那么这种优化可能没有多大价值.

for graphs of max degree O(1), we can make this truly linear-time by maintaining verticesNotYetConsidered intersect neighbors, which I didn't do for the sake of clarity. This optimization probably isn't worth much if you exploit word-parallelism by representing the graph as an adjacency matrix where each row is stored as a one- or two-word bitmap.

这篇关于有效地找到所有连接的诱导子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！