Complessità del tempo di Vertex Cover vs Clique per fisse K

Question

Ho 2 modi per risolvere il problema indipendente del problema di dimensioni fisse $ k $ per grafico $ g= (v,E) $ :
- Algoritmo di copertura vertice in esecuzione in $ o ^ * (1.47 ^ {v - k}) $ (algoritmo ricorsivo ottimizzato) - Algoritmo di clique in esecuzione in $ o ({v \ Select k}) $ (semplici enumerati sottoinsiemi di $ V $ e controllare l'algoritmo)

Come posso determinare quale ha una complessità temporale inferiore?Non ho familiarità con gli algoritmi per i problemi completi di NP e $ o ^ * $ notazione.Tracciare queste funzioni sufficiente?Penso che l'algoritmo VC possa avere qualsiasi classe di polinomio $ n ^ {o (1)} $ come moltiplicazione a causa della $O ^ * $ notazione e questo potrebbe influire sui tempi di corsa, ma non ne sono sicuro.

Answer 1

per qualsiasi classe fissa $ k $ , $ o (\ binom {v} {k})= o (v^ k) $ è polinomiale, mentre $ o ^ * (1.47 ^ {vk})= o ^ * (1,47 ^ V) $ è esponenziale.Le esponenziali crescono molto più veloci dei polinomi.

Tracciare le curve non è così utile, poiché queste sono affermazioni asintotiche.

detto questo, se sei interessato a particolare $ V $ e $ k$ , quindi la tua migliore opzione è quella di verificare empiricamente quale di questi algoritmi è più veloce.La notazione asintotica non è utile qui, poiché nasconde fattori costanti, e questi potrebbero fare una grande differenza per i valori concreti di $ V $ e $ k $ .

Answer 2

Vertex Cover è il parametro fisso tratto. C'è una semplice $ 2 ^ k n $ algoritmo per trovare un VC di dimensioni $ k $ . Questo dovrebbe battere l'algoritmo ingenuo. Lo stato attuale dell'arte è qualcosa come $ 1,24 ^ k n $ .

Sotto alcune ipotesi non c'è algoritmo per K clique con tempo di funzionamento $ f (k) n ^ c $ .

Se il tuo grafico ha una struttura speciale, i risultati possono essere migliorati.