Исследование «критических» наследственных классов в анализе вычислительной сложности задач на графах

Развитие теории сложности вычислений способствовало укоренению пессимистического взгляда на возможность существования эффективных (полиномиальных) алгоритмов для многих задач на графах, представляющих практический и/или теоретический интерес. Одним из возможных способов преодоления алгоритмической сложности таких задач является сужение, т.е. наложение дополнительных ограничений на класс рассматриваемых графов. Иногда учет этих ограничений, т.е. принадлежности графа некоторому классу, приводит к созданию полиномиального алгоритма для решения задачи. В других случаях удается доказать, что задача для графов из того или иного класса остается NP-полной. К настоящему времени накоплено огромное количество фактов того и иного рода. Придать этому процессу целенаправленность и систематичность можно, переходя от рассмотрения отдельных классов к рассмотрению представительных семейств классов. В докладе будут изложены результаты подготовленной докторской диссертации по поиску «линии водораздела» между «простыми» и «сложными» элементами семейства наследственных классов графов.