Характеристики сложности: кликовое число графа многогранника и число прямоугольного покрытия

В 1980-х гг. В. А. Бондаренко обнаружил, что кликовое число графа многогранника во многих случаях соответствует реальной сложности задачи оптимизации на вершинах этого многогранника. Для объяснения этого феномена была предложена теория алгоритмов прямого типа, утверждающая, что кликовое число графа многогранника является нижней оценкой сложности соответствующей задачи в так называемом классе алгоритмов прямого типа. Более того, утверждалось, что этот класс является достаточно широким, включающим в себя многие классические комбинаторные алгоритмы. В настоящей работе приводится несколько примеров, призванных обозначить границы применимости этой теории. В частности, описана довольно часто используемая на практике модификация алгоритмов, выводящая их из указанного класса (порядок трудоемкости при этом не меняется). Другой, значительно более близкой к реальности, комбинаторной характеристикой сложности является число прямоугольного покрытия матрицы инциденций фасет-вершин, введенное в рассмотрение М. Яннакакисом в 1988 г. Мы приводим пример многогранника с полиномиальным (относительно размерности многогранника) значением этой характеристики, задача оптимизации на вершинах которого NP-трудна.