Algoritmo set indipendente massimo

Question

Non credo esista un algoritmo per trovare il massimo vertice indipendente impostato in un grafico bipartito diverso dal metodo della forza bruta per trovare il massimo tra tutti i possibili insiemi indipendenti.

Mi chiedo se lo pseudocodice trovi tutti i possibili set di vertici.

Dire un grafico bipartito con 4 vertici blu e 4 rossi. Attualmente mi

Start with an arbitrary blue, 
    find all red that don't match this blue 
    put all these red in Independent Set 
    find all blue that dont match these red 
    put these blue in Independent Set 
    Repeat for next vertex in blue 

Repeat all over again for all blue then all vertices in red. 

Capisco che in questo modo non mi dà tutte le possibili combinazioni insieme indipendente a tutti, dal momento che dopo il primo passo ho scelto tutti i prossimi vertici colore che dont partita, piuttosto che fare un passo attraverso ogni possiblity.

Per esempio dato un grafico con la corrispondenza

B R 
1 1 
1 3 
2 1 
2 3 
3 1 
3 3 
4 2 
4 4 

Start with blue 1 
    Choose red 2 and 4 since they dont match 
    Add 2, 4 to independent Set 
    Choose 2 and 3 from blue since they dont with 2 or 4 from red 
    Add 2 and 3 from blue to independent set as well. 
Independent Set = 1,2,3 from blue 2,4 from red 
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set) 

C'è un modo posso migliorare questo algoritmo per una migliore ricerca di tutte le possibilità. So che a | Set massimo per un grafico bipartito | = | Rosso | + | Blu | - | Corrispondenza massima |.

Il problema sorge con la possibilità che scegliendo tutti i possibili rossi al primo tentativo per un dato blu, se quelli rossi si collegano a tutti gli altri blu possibili, il mio set ha sempre solo 1 blu e resto rosso.

Answer 1

Non credo esista un algoritmo per trovare il massimo vertice indipendente impostato in un grafico bipartito diverso dal metodo della forza bruta per trovare il massimo tra tutti i possibili insiemi indipendenti.

C'è: trovare la massima impostata indipendente è equivalente a trovare la copertura minima vertice (prendendo il complemento del risultato), e Konig's theorem afferma che copertura minima vertice in grafi bipartiti è equivalente alla massima corrispondenza, e che tale può essere trovato in tempo polinomiale. Non so di trovare tutti gli abbinamenti, ma sembra che ci possano essere molti esponenzialmente.

Answer 2

Come Aaron McDaid menziona nella sua risposta ora cancellata, il problema di trovare un set indipendente massimo equivale a trovare una clique massima. L'equivalenza è che trovare un insieme massimo indipendente in un grafico G equivale a trovare una cricca massima nel complemento di G. Il problema è noto per essere NP-completo.

La soluzione di forza bruta che citi prende O(n^2 2^n), ma puoi fare meglio di così. Robson ha un documento intitolato "Algoritmi per i set indipendenti massimi" del 1986 che fornisce un algoritmo che prende 0<c<1 (credo che c sia circa 1/4, ma potrei sbagliarmi). Questo non è specifico per un grafico bipartito .

una cosa da notare, se si dispone di un grafo bipartito è che entrambi i lati forma un insieme indipendente. in caso di totale grafo bipartito K_{b,r} che è partizionato B x R con |B|=b e |R|=r in cui v'è un vantaggio da ogni vertice in B ad ogni vertice in R e nessuno all'interno di B né nessuno all'interno di R, un set indipendente massimo è B se b>=r, altrimenti è R.

L'utilizzo di B o R non funziona in generale.sdcvvc ha notato l'esempio con i vertici {1,2,3,A,B,C} e gli spigoli {A,1}, {A,2}, {A,3}, {B,3}, {C,3}. In questo caso, il set indipendente massimo è {1,2,B,C}, che è più grande di entrambe le partizioni {A,B,C} o {1,2,3}.

Si può migliorare l'algoritmo di Robson per iniziare con il più grande di B o R e procedere da lì, anche se non sono sicuro di quanto possa fare questa differenza.

In alternativa, è possibile utilizzare Hopcroft–Karp algorithm sul complemento bipartito di un grafico per trovare una corrispondenza massima, quindi prendere i vertici utilizzati nell'associazione come set indipendente. Questo dà un algoritmo del tempo polinomiale per risolvere il problema.