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

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