Un $\gamma$-quasi-clique, pour $0<\gamma< 1$, dans un graphe simple non-orienté est un sous-ensemble de sommets dont le sous-graphe induit a une densité d'arêtes supérieure ou égale à $\gamma$. Un ensemble de $\gamma$-quasi-cliques couvrant toutes les arêtes d'un graphe est appelé une couverture par des $\gamma$-quasi-cliques. Le problème de couverture minimale par des $\gamma$-quasi-cliques consiste à trouver une couverture par des $\gamma$-quasi-cliques ayant le plus petit nombre de quasi-cliques. Une partition des sommets d'un graphe par des quasi-cliques est un ensemble de $\gamma$-quasi-cliques telle que chaque sommet du graphe appartient à un seul quasi-clique de l'ensemble. Le problème de partition minimale par des $\gamma$-quasi-cliques consiste à trouver une partition par des $\gamma$-quasi-cliques ayant le plus petit nombre de quasi-cliques. Nous démontrons que les problèmes de décision associés aux problèmes de couverture minimale et partition minimale par des $\gamma$-quasi-cliques sont NP-complets pour tout $\gamma$ satisfaisant $0<\gamma<1$ fixé.