О сложности некоторых задач на наследственных классах графов

Рассматриваются задачи о независимом множестве, о доминирующем множестве и о длиннейшем пути для классов графов, определяемых конечными множествами запрещенных подграфов. Доказано, что, если среди запрещенных имеется граф, у которого каждая компонента связности гомеоморфна $K_2$ или $K_{1,3}$, из трех задач решается для графов из такого класса за полиномиальное время. Если же таких запрещенных графов нет, то все три задачи остаются NP-трудными.