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

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

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

Во всех рассмотренных случаях полиэдральные характеристики коррелируют со сложностью задачи.