Efficiently find all connected induced subgraph

Question

Czy istnieje skuteczny algorytm (*), aby znaleźć wszystkie połączone (wywołane) podgrafy połączonego nieokreślonego wykresu z wierzchołkami?

(*) Rozumiem, że w ogólnym przypadku każdy taki algorytm może mieć złożoność O (2^n), ponieważ dla kliki (Kn) istnieją 2^n połączone podgraphy. Jednak wykresy, z którymi zazwyczaj mam do czynienia, będą miały o wiele mniej połączonych podgrafów, więc szukam sposobu na ich wygenerowanie bez rozważenia wszystkich 2^n podgraphów i wyrzucenia tych, które nie są połączone (jak w rozwiązanie do this question).

Algorytm, który ma czas działania liniowy pod względem liczby rozwiązań (tzn. Może generować rozwiązania bezpośrednio ze struktury wykresu bez marnowania czasu z uwzględnieniem wszystkich rozwiązań innych niż rozwiązania) byłby oczywiście idealny. Dodatkowy krok, który jest wielomianem w liczbie węzłów, również byłby w porządku (np. Wstępne obliczenie przechodniego zamknięcia wykresu - nie to, jak sądzę, byłoby pomocne w tym przypadku).

Alternatywnie, dowód, że nie ma takiego rozwiązania, przynajmniej wyrzuciłby mnie z mojej nędzy.

Answer 1

W rekurencyjnego Pseudokod The^algorytm n2 wynosi

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

nie ma znaczenia, który wierzchołek V jest wybrany; możemy nawet wybrać inaczej w dwóch rozmowach z rodzeństwem. Wykorzystujemy tę swobodę, aby uzyskać algorytm prawie liniowy (n razy liczbę rozwiązań) przez przycięcie drzewa rekursji.

Jeśli subsetSoFar jest pusty, wybór nadal pozostaje nieograniczony. W przeciwnym razie wybieramy v, aby przylegać do jednego z wierzchołków w subsetSoFar. Jeśli nie ma takiego v, otrzymujemy subsetSoFar i wrócimy, ponieważ nie ma innych rozwiązań w tym poddrzewie.

Należy zwrócić uwagę na nowy niezmiennik, że subsetSoFar jest zawsze podłączony, dzięki czemu możemy wyeliminować jawny test łączności. Wykonujemy O (n) pracę w każdym węźle drzewa rekursji (naiwnie O (n^2), ale możemy utrzymywać zbiór sąsiadujących wierzchołków przyrostowo), który jest kompletny binarny i którego liście dają dokładnie jedno rozwiązanie, więc suma praca jest jak twierdzono (przypominam, że liczba wewnętrznych węzłów jest o jeden mniej niż liczba liści).

Ze względu na nowy niezmiennik, nie powstaje odłączony subgraph.

Każdy podłączony subgraph jest poddawany. Dla zestawu wierzchołków S, które indukuje podłączony subgraph, podążaj za gałęziami, które zgadzają się z S. Nie jest możliwe, aby właściwy podzbiór S nie był przyległy do ​​reszty S, więc S nie jest przycinany.

Nowy pseudokod jest następujący. N(v) oznacza zbiór sąsiadów 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: na wykresach maksymalny stopień O (1), możemy zrobić to naprawdę liniowy czas utrzymując verticesNotYetConsidered intersect neighbors, czego nie robić dla jasności. Ta optymalizacja prawdopodobnie nie jest wiele warta, jeśli wykorzystasz paralelizm wyrazów, reprezentując wykres jako macierz sąsiedztwa, gdzie każdy wiersz jest zapisany jako mapa bitowa jedno- lub dwuliterowa.