Минимальная бисекция: различия между версиями

В настоящее время существует большой разрыв между коэффициентом аппроксимации O(log n) для задачи о минимальной бисекции, полученным в результате применения теоремы 1, и сложностью известных для него результатов аппроксимации. Как упоминалось выше, задача о минимальной бисекции является NP-полной [9].

Неизвестно, является ли эта задача APX-полной, однако некоторые результаты позволяют предположить такую возможность. Буй и Джонс [4] показали, что для любого фиксированного значения e > 0 задача аппроксимации минимальной бисекции с дополнительным членом и2~е будет NP-полной. Фейге [ ] показал, что если опровержение для задачи выполнимости булевых формул в k-конъюнктивной нормальной форме в случае k=3 является сложным в среднем на реальном распределении входных данных, то для любого фиксированного значения " > 0 не существует алгоритма 4/3-аппроксимации задачи о минимальной бисекции. Хот [ ] доказал, что для нахождения минимальной бисекции неприменима схема аппроксимации с полиномиальным временем выполнения (PTAS), за исключением случая, если класс NP включает рандомизированные алгоритмы с субэкспоненциальным временем выполнения.

Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества V = A [ B [ S, где |S| насколько возможно мало, при соблюдении следующего ограничения: max fjAj; jBjg < n/2 и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить алгоритм аппроксимации с полилогарифмическим коэффициентом для решения этой задачи. Стоит отметить, что на тот же вопрос, касающийся версии задачи о минимальной бисекции для ориентированных графов, Фейгеи Яхалом дали отрицательный ответ [8].