12

接続された無向頂点ラベル付きグラフのすべての接続された（誘導された）サブグラフを見つけるための効率的な（*）アルゴリズムはありますか？

（*）一般的なケースでは、クリーク（Kn）の場合、2 ^ nの接続されたサブグラフがあるため、このようなアルゴリズムはO（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が選択されているかは関係ありません。2つの兄弟呼び出しで異なる方法を選択することもできます。この自由度を利用して、再帰ツリーを枝刈りすることにより、ほぼ線形時間のアルゴリズム（解の数のn倍）を取得します。

が空の場合subsetSoFar、選択肢はまだ制約されていません。vそれ以外の場合は、の頂点の1つに隣接することを選択しますsubsetSoFar。そのようなものが存在しない場合、このサブツリーには他のソリューションがないため、v降伏して戻ります。subsetSoFar

常に接続されている新しい不変条件に注意してくださいsubsetSoFar。これにより、明示的な接続テストを排除できます。再帰ツリーの各ノードでO（n）作業を行います（単純にO（n ^ 2）ですが、隣接する頂点のセットを段階的に維持できます）。これは完全なバイナリであり、それぞれの葉が正確に1つの解を生成するため、合計作業は主張どおりです（内部ノードの数はリーフの数より1つ少ないことを思い出してください）。

新しい不変量のため、切断されたサブグラフは生成されません。

接続された各サブグラフが生成されます。接続された部分グラフを誘導する頂点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、明確にするために私がしなかったを維持することによって、これを真に線形な時間にすることができます。グラフを隣接行列として表現することで単語の並列処理を活用する場合、この最適化はおそらくあまり価値がありません。隣接行列では、各行が1語または2語のビットマップとして格納されます。

于 2013-03-27T13:02:26.550 に答える