Wiele trudnych problemów algorytmicznych może być rozwiązane wydajniej w węższym zakresie sytuacji. Przykładem takiego podejścia jest rozważanie nie grafów dowolnych, ale tylko tych nie zawierających określonej podstruktury.

W swoim referacie zaprezentuję wyniki dotyczące trudności problemu zbioru niezależnego w klasach grafów uporządkowanych wolnych od określonych podgrafów indukowanych. Przy pomocy odpowiednich redukcji wskażę szereg przypadków NP-trudnych, a poprzez konkretne algorytmy i wnioski strukturalne zidentyfikuję przypadki, które można rozwiązać w czasie wielomianowym.