Исследование полиэдральных графов комбинаторных задач

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