Trova tutti i sottotitoli indotti connessi

Question

Esiste un efficiente algoritmo (*) per trovare tutti i sottografi (indotti) connessi di un grafo etichettato con vertice non orientato collegato?

(*) Apprezzo che, nel caso generale, qualsiasi algoritmo di questo tipo possa avere complessità O (2^n) perché, per una cricca (Kn), esistono 2 sottotitoli connessi. Tuttavia, i grafici con cui sto trattando in genere avranno molti meno sottografi connessi, quindi sto cercando un modo per generarli senza dover considerare tutti i sottotitoli 2^n e buttare via quelli che non sono collegati (come nel soluzione a this question).

Un algoritmo che ha un tempo di esecuzione lineare nel numero delle soluzioni (ovvero può generare le soluzioni direttamente dalla struttura del grafico senza perdere tempo considerando tutte le non soluzioni) sarebbe ovviamente l'ideale. Un passo aggiuntivo che è polinomiale nel numero di nodi andrebbe bene (ad esempio pre-calcolare la chiusura transitiva del grafico - non che penso che sarebbe di aiuto in questo caso).

In alternativa, una prova che non esiste tale soluzione mi metterebbe almeno fuori dalla mia sofferenza.

Answer 1

In pseudocodice ricorsiva, l'algoritmo^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}) 

non importa quale v vertice viene scelto; possiamo persino scegliere diversamente in due chiamate fratello. Sfruttiamo questa libertà per ottenere un algoritmo quasi lineare (n volte il numero di soluzioni) potando l'albero di ricorsione.

Se subsetSoFar è vuoto, la scelta non è ancora vincolata. Altrimenti, scegliamo v per essere adiacenti a uno dei vertici in subsetSoFar. Se non esiste tale v, restituiamo subsetSoFar e restituiamo, poiché non ci sono altre soluzioni in questa sottostruttura.

Nota il nuovo invariante che subsetSoFar è sempre connesso, quindi è possibile eliminare il test di connettività esplicita. Facciamo O (n) lavoro su ogni nodo dell'albero di ricorsione (ingenuamente O (n^2) ma possiamo mantenere l'insieme di vertici adiacenti in modo incrementale), che è completo binario e le cui foglie producono ciascuna esattamente una soluzione, quindi il totale il lavoro è come sostenuto (ricorda che il numero di nodi interni è uno in meno del numero di foglie).

In base alla nuova variabile inversa, non viene fornito alcun sottografo disconnesso.

Ogni sottografo connesso viene restituito. Per un insieme di vertici S che induce un sottografo collegato, segui i rami che concordano con S. Non è possibile che un sottoinsieme appropriato di S non abbia alcuna adiacenza al resto di S, quindi S non viene potato.

Il nuovo pseudocodice è il seguente. N(v) indica il set di vicini di 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: per i grafici di grado massimo O (1), siamo in grado di rendere questo veramente tempo lineare mantenendo verticesNotYetConsidered intersect neighbors, che non ho fatto per motivi di chiarezza. Questa ottimizzazione probabilmente non vale molto se si sfrutta il parallelismo delle parole rappresentando il grafico come una matrice di adiacenza in cui ogni riga è memorizzata come bitmap a una o due parole.