Il problema K-cLique è diventato più facile sui grafici sparsi?

Question

Alcune definizioni, solo per non creare confusione:

1. UN grafico sparso è un grafico che contiene un numero di bordi in meno o uguale al numero di vertici.

2. In $ k $ -Clique Problema Ci viene dato un grafico e un numero intero $ k $ e l'attività è decidere se il grafico contiene una clique $ k $.

Penso che anche se abbiamo un grafico sparso, nulla cambia per il problema $ k $ -Clique (ha sempre complessità $ o (n^k) $ se $ k $ è inferiore al numero di vertici e ha complessità $ o (n^n) $ se $ k $ è uguale al numero di vertici), ma non ne sono così sicuro.

Una clique $ k $ è più facile da trovare se il grafico è scarso?