Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов

В данной работе рассматриваются понятия минимального сложного и граничного классов. Данные классы играют особую роль при определении границы между полиномиальной разрешимостью и $NP$-полнотой задач на графах в семействе наследственных классов. Ранее в одной из работ автора было установлено, что для некоторого типа задач на графах минимальных сложных классов нет. В данной работе, наоборот, доказывается достаточное условие существования таких классов. Его действенность подтверждается новыми примерами минимальных сложных классов и граничных классов для некоторых задач на графах. Для выявленных задач удается полностью описать множества минимальных сложных и граничных классов. Ранее ни для одной задачи на графах таких описаний получить не удавалось.
Работа выполнена при поддержке РФФИ, проекты 10–01–00357-a и 11–01–00107-a, и ФЦП “Научные и научно-педагогические кадры инновационной России на 2009–2012 гг.”, ГК 16.740.11.0310.