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

В докладе мы продемострируем метод получения сложный отношений, в смысле коммуницационной сложности, из функций с большой "block sensetivity".
Также покажем применение данного метода в сложности доказательств.

Есть ансамбль практических задач, которые мы умеем решать за полиномиальное время. Однако, почти везде наивный алгоритм является наиболее быстрым для этих задач и существенное
улучшение этих алгоритмов открытая задача. Есть три популярные гипотезы, которые позволяют доказывать нижние оценки (в предположении трудности классических задач) на время работы алгоритмов: SETH, APSP не решается за субкубическое время, 3SUM не решается за субквадтратичное время. Планируется рассказать о различных задачах на графах и что они не легче чем APSP. Например, почему найти все треугольники отрицательного веса в графе не легче чем посчитать все кратчайшие расстояния между парами вершин. В некоторых задачах даже поиск приближенного решения с константной ошибкой не легче поиска точного решения и причины этого мы тоже постараемся узнать.