Problem Casanovy Graf Znajomości

[Avicularia]

Cześć, nie wiem czy pisze w dobrym dziale, ale mam takie zadanie do rozwiązania i byłbym bardzo wdzięczny za pomoc i wytłumaczenie:
Osobnik ma znajomych, spośród których niektóre się znają. Chce jednocześnie umawiać się
z \(\displaystyle{ k}\) osobami z kręgu swoich znajomych. Aby zminimalizować niebezpieczeństwo dekonspiracji chce, aby te osoby nawzajem się nie znały.
Problem Casanovy rzędu \(\displaystyle{ k}\), zwany potocznie \(\displaystyle{ k-Kazik}\), polega na tym, aby mając graf znajomości i liczbę \(\displaystyle{ k}\), rozstrzygnąć, czy jest to możliwe.

[Mruczek]

Trzeba po prostu stwierdzić czy w tym grafie jest zbiór niezależny o wielkości \(\displaystyle{ k}\). No a to jest problem NP-zupełny.

[Avicularia]

Wiem, tylko jak to uzasadnić.

[Cytryn]

Problem znalezienia największego takiego zbioru jest NP-trudny, a jeśli zadowolimy się rozmiarem \(\displaystyle{ k}\)? Co wtedy?

[Avicularia]

Nie mam pojęcia kompletnie jak się d tego zabrać, a zależy mi na rozwiązaniu tego. Nie jest w stanie mi ktoś tego łopatologicznie wytłumaczyć?