Le problème K-Cique est-il devenu plus facile sur les graphiques clairsemés?

Question

Certaines définitions, juste pour ne pas créer de confusion:

1. UN graphique clairsemé est un graphique qui contient un nombre de bords moins ou égal que le nombre de sommets.

2. Dans PROBLÈME $ K $-CLIQUE On nous donne un graphique et un entier $ k $, et la tâche consiste à décider si le graphique contient un $ k $ -clique.

Je pense que même si nous avons un graphique clairsemé, rien ne change pour le problème $ k $ -clique (il a toujours une complexité $ o (n ^ k) $ si $ k $ est inférieur au nombre de sommets et qu'il a une complexité $ o (n ^ n) $ si $ k $ est égal au nombre de sommets), mais je n'en suis pas si sûr.

Un $ k $ -clique est-il plus facile à trouver si le graphique est clairsemé?