Effizient alle verbundenen induzierten Subgraphen finden

Question

Gibt es einen effizienten (*) Algorithmus, um alle verbundenen (induzierten) Teilgraphen eines verbundenen ungerichteten Vertex-markierten Graphen zu finden?

(*) Ich schätze, dass ein solcher Algorithmus im allgemeinen Fall O (2^n) -Komplexität haben kann, weil es für eine Clique (Kn) 2^n zusammenhängende Teilgraphen gibt. Die Graphiken, mit denen ich normalerweise zu tun habe, werden jedoch viel weniger verbundene Subgraphen haben, also suche ich nach einer Möglichkeit, sie zu generieren, ohne alle 2^n-Untergraphen zu berücksichtigen und diejenigen, die nicht verbunden sind, wegzuwerfen (wie in der Lösung zu this question).

Ein Algorithmus mit einer linearen Laufzeit in der Anzahl der Lösungen (d. H. Er kann die Lösungen direkt aus der Struktur des Graphen generieren, ohne Zeit unter Berücksichtigung aller Nicht-Lösungen zu verschwenden) wäre offensichtlich ideal. Ein zusätzlicher Schritt, der ein Polynom in der Anzahl der Knoten ist, wäre ebenfalls in Ordnung (z. B. Vorberechnung der transitiven Schließung des Graphen - nicht dass ich denke, dass dies in diesem Fall helfen würde).

Alternativ würde ein Beweis, dass es keine solche Lösung gibt, mich zumindest aus meinem Elend bringen.

Answer 1

in rekursiven Pseudo-Code, der 2^n-Algorithmus ist

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}) 

Es spielt keine Rolle, welche Knoten v ausgewählt ist; wir können sogar in zwei Geschwisteranrufen anders wählen. Wir nutzen diese Freiheit aus, um durch Beschneiden des Rekursionsbaums einen Algorithmus mit nahezu linearer Zeit (n-mal die Anzahl der Lösungen) zu erhalten.

Wenn subsetSoFar leer ist, ist die Auswahl immer noch nicht eingeschränkt. Ansonsten wählen wir v als benachbart zu einem der Vertices in subsetSoFar. Wenn kein v existiert, geben wir subsetSoFar zurück und zurück, da es in diesem Teilbaum keine anderen Lösungen gibt.

Beachten Sie die neue Invariante subsetSoFar ist immer verbunden, so dass wir den expliziten Konnektivitätstest beseitigen können. Wir arbeiten O (n) an jedem Knoten des Rekursionsbaums (naiv O (n^2), aber wir können die Menge benachbarter Knoten inkrementell pflegen), was komplett binär ist und dessen Blätter jeweils genau eine Lösung liefern, also die Summe Arbeit ist wie beansprucht (erinnern Sie sich, dass die Anzahl der internen Knoten um eins weniger ist als die Anzahl der Blätter).

Aufgrund der neuen Invariante wird kein getrennter Untergraph erhalten.

Jeder verbundene Teilgraph wird ausgegeben. Für eine Menge von Knoten S, die einen verbundenen Teilgraphen induzieren, folgen Sie den Zweigen, die mit S übereinstimmen. Es ist nicht möglich, dass eine richtige Teilmenge von S keine Nachbarschaft zum Rest von S hat, also wird S nicht beschnitten.

Der neue Pseudocode ist wie folgt. N(v) bezeichnet den Satz von Nachbarn von 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)) 

EDIT: für Graphen von max Grad O (1), können wir diese wirklich linear-Zeit, indem verticesNotYetConsidered intersect neighbors beibehalten, die ich nicht aus Gründen der Klarheit tat. Diese Optimierung ist wahrscheinlich nicht viel wert, wenn Sie die Wortparallelität ausnutzen, indem Sie den Graphen als Adjazenzmatrix darstellen, in der jede Zeile als Ein- oder Zwei-Wort-Bitmap gespeichert wird.