Définir le problème de la couverture avec des ensembles de taille 2

Question

J'ai une question sur le problème de la couverture définie: si j'obtiens un univers Univers $ U $ et $ M $ sous-ensembles de taille exactement 2 $, et un entier $ k $. Ce problème est-il toujours NP-C ou je peux le résoudre à un temps polynomial?

Merci.