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

В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали алгоритм аппроксимации по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего алгоритма аппроксимации со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый алгоритм аппроксимации солиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом.

(Алгоритм аппроксимации по двум критериям разбивает вершины на два множество, каждое из которых содержит не более 2/3 вершин, и его значение (т.е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера).

В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза <math>(S, \bar{S}) \;</math>, такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число <math>r \ge 2 \;</math> – или разделить граф на r фрагментов размерами <math>k_1,... , k_r \;</math>, где числа <math>k_i \;</math> заранее заданы во входных данных; и в том и в другом случае задача заключается в минимизации количества ребер между различными фрагментами.

Задача 3. Заранее заданное разбиение

Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа k1, ... , kr, такие, что Pi ki = j Vj.

Требуется: найти разбиение V = V 1 • • • U Vr графа G с j V i j = ki для всех i, такое, что общий вес ребер, конечные точки которых принадлежат к разным множествам Vi, насколько возможно мал.

Фейге и Краутхамер [ ] предложили алгоритм аппроксимации для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации O(log 2n), поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [ ], авторы улучшили коэффициент до O(log '  и).

Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом O(log1:5 n). Более конкретно, алгоритм создает для входного графа G бисекцию (S, S), стоимость которой не превышает O(log1:5 n) ■ b(G).

Теорема 2. Задача о сбалансированном разрезе (и, в частности, о реберном сепараторе может быть приближенно решена за полиномиальное время с коэффициентом O(log1:5 n).

Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время nO(r) с коэффициентом O(log1:5 n).

Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, /3-сбалансированном сечении и запранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).

Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [ 6].

 

Алгоритм аппроксимации по двум критериям для нахождения f$-сбалансированного разреза возвращает разрез, являющийся /^'-сбалансированным для заранее определенного значения /}' > p. Например, для бисекции, P = 1/2; обычно P' = 2/3.

 

Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм аппроксимации для решения задачи о минимальной бисекции в k-однородных гиперграфах [ ]; (2) алгоритм аппроксимации для варианта задачи о минимальном множественном разрезе [ ]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5].

 

В настоящее время существует большой разрыв между коэффициентом аппроксимации 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].

 

*'' [[Самое неплотное сечение]]