Назад в библиотеку

Случайное разделение. Новый метод решения оптимизационных задач фиксированной мощности

  Авторы: Leizhen Cai, Siu Man Chan, Siu On Chan
  Источник: Оригинальная статья на английском языке  [Перейти]

   Аннотация

Leizhen Cai, Siu Man Chan, Siu On Chan. Случайное разделение. Новый метод решения оптимизационных задач фиксированной мощности. Описание разработанного нового рандомизированного метода – случайное разделение, для решения оптимизационных задач фиксированной мощности на графах.


   Общая постановка проблемы

Мы разрабатываем новый рандомизированный метод – случайное разделение, для решения оптимизационных задач фиксированной мощности на графах, т.е. проблем, касающихся решений с точно фиксированным к числом элементов (например, к вершин V), которые оптимизируют решение значения (например, число ребер покрыты V). Основная идея метода состоит в разделении множества вершин графа на два непересекающихся множества отдельных компонент связности, а затем выберите соответствующий компонентов с соответствующим решением. Мы можем использовать универсальные наборы алгоритмов, полученных из этого метода.

Этот новый метод является универсальным и мощным, как он может быть использован для решения широкого спектра оптимизационных задач фиксированной мощности для графов со степенным ограничением, вырожденных ограниченных графов (большая семья графов, содержит графы со степенным ограничением , плоские графы, мелкие закрытые семейства графов) и даже общих графов.

   1. Введение

   1.1. Мотивация и похожие работы

Много NP-трудных задач, когда некоторая часть входных I  взята  в качестве фиксированного параметра к для формирования фиксированных параметров проблемы, может быть решена путем алгоритмов, которые равномерно работают в полиномиальное время, то есть F (K) | I | O (1),  время для некоторой функции F (K). Известные примеры таких алгоритмов: O (N 3) – алгоритмы Робертсона и Сеймура для решения гомоморфизма подграфов  и O (N) – алгоритм Bodlaender для нахождения разложения дерева ширины K, также O (N) – алгоритмы Courcelle и Arnborg  для решения проблемы вырождающиеся  монодинамической логики второго порядка на графах дерева ширины к, еще  O (кn + 1. 286 k) – алгоритмы Чена, Kanг и Цзя для нахождения вершинного покрытия К вершин. Дауни и Феллов установили общую основу для изучения сложности фиксированных параметрических задач. В этой статье, мы разрабатываем новый рандомизированный метод, называемый случайным разделением, для проектирования равномерно полиномиальных алгоритмов для решения задач на графах с фиксированным параметром, особенно оптимизационных задач с фиксированной мощностью. Оптимизационные задачи с фиксированной мощностью являются проблемой, которая требует для решения с точно фиксированным к - числом элементов (например, к вершин V) оптимизировать решение значения (например, число ребер покрыты V), а  Цай инициировала систематическое изучение оптимизационных задач с фиксированной мощностью точки зрения сложности. Основная идея нашего метода случайного разделения является случайное разделение множества вершин графа на два непересекающихся множества для разделения графа на подключенные компоненты, а затем выбрать соответствующие компоненты с образованием решения. Мы можем использовать универсальные наборы алгоритмы, полученные из этого метода. 

Наше первоначальное вдохновения для разработки метода случайного разделения пришло от цветового кодирования методом Алона, Ястера и Цвика для решения фиксировано-параметрических задач на графах. Основной идеей их метода является случайная раскраска вершин  в K-цвета, а затем поиск красочного K-решения, т.е. решения, состоящего из вершин К в различных цветах. Чтобы дерандомизировать алгоритм, они используют идеальную хэш-функцию. Они используют цветовое кодирование, чтобы найти, для каждом фиксированной К, К-путь за O (N) время и O (N log N) в худшем случае, K-цикла за O (N α ) время и O (N α log N) в худшем случае, где α <2,376. Подграф, изоморфный K-вершинному графу H дерева шириной W находят в планируемое время  O (N W +1 ) и O (N log  N) в худшем случае. К сожалению, в большинстве фиксированных параметрических задач, очень трудно найти красочные K-решения, что значительно ограничивает применимость цвета кодирования. С другой стороны, намного легче иметь дело с подключенными компонентами, которые позволяют использовать случайные разделения, решать широкий спектр проблем с фиксированными параметрами, особенно когда входной граф имеет ограниченную степень или вырождение.

На самом деле, это довольно удивительно, что мы можем использовать случайные фиксаторы для придания равномерно полиномиальным алгоритмам классов фиксированных параметрических задач, особенно задач оптимизации фиксированной мощности, на графах ограниченной степени.

Для дерандомизации, нашими главными инструментами являются универсальные наборы и совершенная хэш-функция. Набор двоичных векторов длины п, где (N, T) – универсальные, если для каждого подмножество размера т из индексов, все T  вида 2т. Наор, Шульман и Сринивасан имеют детерминированный для строительства (N, T) – универсальных наборов размер 2 T T O (log т) log N, которые могут быть перечислены в линейное время. Семьи F отображающих функций размером N в диапазон размеров К-семейство совершенной хэш-функции, если для любого подмножества S размера К из области, существует функция F, то есть 1-к-1 на S. На основе работ Г. Шмидта и Зигеля [13] и указаний от Мони Naor, (n, к)-семейство совершенной хэш-функции размером 2O (K) log N может быть детерминировано и построено за линейное время.

После Дауни и Феллов, мы говорим, что фиксированный параметр решения проблемы является послушным, если он имеет равномерно полиномиальное время, и  неразрешимым, если W [I]-сложно для некоторых W [I] в W-иерархии. Заметим, что W [I]-трудная задача не может быть решена в равномерно полиномиальное время, если все проблемы в W [I] не могут быть решены в равномерно полиномиальное время.

   1.2 Основные результаты

Мы ориентируемся на графы с ограниченной степенью вырождения или проблемах с фиксированными параметр для общих графов. Ограниченная степень представляет собой граф, в котором максимальная степень ограничена константой D. Граф G является D-вырожденным, если каждый индуцированный подграф графа G есть вершина степени не выше D. Легко видеть, что каждый D-вырожденный граф допускает такую ациклическую ориентацию, что исходящая степень каждой вершины не превосходит D. Много интересных семейств графов являются D-вырожденными для некоторого фиксированного постоянного D. Например, графы на некоторой встраиваемой фиксированной поверхности (плоские графы являются 5-вырожденными), графы с ограниченной степенью, графы с ограниченной шириной дерева, и нетривиальные мелкие закрытые семейства графов.

В этой статье мы покажем мощность случайного метода разделения по следующим результатам:

1. Для степени, ограниченной графом G, получаем равномерно полиномиальный алгоритм для широкого круга основных параметров проблемы, который просит найти K  вершин (ребер) S  до оптимизации значения φ (S), т.е.  определяется целевая функция φ, равномерно вычисляемая в полиномиальное время.

2. Для каждой степени, ограниченной графом G и каждого K-вершинного графа Н, можно найти максимум (минимум) веса индуцированного (частично) H-подграфа в G  за O (N log N) время для каждого фиксированного к.

 3. Для каждого фиксированного к, мы можем найти некоторое подмножество вершин в общем графе, чтобы покрыть ровно к ребер за О (т + п log п) время.

4. Для каждой к-вершины дерева (леса) H и фиксированных к и d, мы можем найти индуцированный H-подграф в D-вырожденным графе за O (N) время и O (N2 log 2 N) в худшем случае.

5. При фиксированном к и d, мы можем найти K-индуцированный цикл в D-вырожденном графе за  О (п 2 ) время и O (N 2 log 2 N) в худшем случае.

Кроме того, можно также использовать случайное разделения решения проблемы фиксированным параметром на выполнимость, переключение упаковки и покрытия, и многих других, когда входной параметр подчиняется некоторой степени ограничений, которые будут обсуждаться далее.

   1.3 Обозначения и организация

Мы используем G = (V, E) для обозначения входного графа (или орграфа) с п вершинами и m краями. Для графа H, его вершины (ребра)  обозначаются через V (H) (соответственно E (H)). Для подмножества вершин V, NG (V) обозначает окрестности V, т.е. множество вершин не в V, которые являются смежными некоторых вершин в V, и N G+ (V) из окрестности V, то есть вершины, не в V, которые являются главами ребер, соединенных с некоторых вершин в V. Для подграфа H, мы используем NG (H) в качестве сокращение для NG (V (H)) и N G+ (H) для N G+ (V (H)). Мы используем DG (У) для обозначения степени вершины V в G. Подграф в G, изоморфный графа H является Н-подграф. Для двух вершин U и V, DG  (U,V) обозначает их расстояние в G и в двух подграфах H 1 и H 2 из G, DG (H1, H2) обозначает их расстояние в G, т. е. DG (H1, H2) = мин { DG (U, V) | U  V (H1), V  V (H2 )}.

В разделе 2 мы вводим основной метод случайного разделения вместе с несколькими рабочими примерами. Далее метод обобщен для решения широкого спектра задач оптимизации с фиксированной мощностью и графами с ограниченной степенью. Также мы объединяем случайное разделение с цветной маркировкой, чтобы найти индуцированные K - вершины деревьев (леса) и индуцированные К-циклы для D-вырожденных графов.

   2. Случайное разделение

Основная идея нашего метода случайного разделения заключается в использовании случайного раздела вершин V  графа G = (V, E), чтобы разделить решение остальной части G на связные компоненты, а затем выбрать соответствующие компоненты из набора. Если быть точными, мы выбираем цвет каждой вершины случайно и независимо, либо зеленый, либо красный, чтобы определить случайное разбиение V в зеленые вершины Vg и красные вершины VR , которые формируют зеленый подграф Gg = G [Vg] и  красный подграф GR = G [VR ]. Для решения S с вершинами К имеется 2 - (К + | NG (S) |) вероятность того, что случайное разбиение обладает свойством S в зеленом подграфе Gg и его окрестности Ng(S) и в красном подграфе GR , т.е. S состоит из набора компонент связности Gg, называемых зелеными компонентами. Для такого раздела, мы обычно можем найти соответствующую коллекцию зеленых компонентов с образованием требуемого к  с помощью стандартного динамического алгоритма программирования для задачи о ранце (см. Книга Клейнберг и Tardos) . Таким образом, с вероятностью 2 - (К + | NG  (S) |) , мы можем найти необходимое K-решение от случайного разбиения. Чтобы дерандомизировать алгоритм, мы используем (N, T)-универсальные наборы для T = K + |  NG (S) |. Общее время всего алгоритма  при условии T ограничено функцией от к.

         Приведем несколько примеров для иллюстрации этого метода в оставшейся части этого раздела.

   2.1 Плотные K-вершинные подграфы в  графах с ограниченной степенью

Начнем с задачи о нахождении подграфа с К вершинами, который содержит максимальное количество ребер. Пусть  d  - фиксированная постоянная и G = (V, E) – граф с максимальной степенью D. Сначала мы случайно красим каждую вершину из G либо в зеленый, либо в красный, чтобы сформировать случайное разбиение (V G , V R) из V.  Пусть G * является максимально К-индуцированный вершинами подграф графа G. Раздел V является «хорошим разделом» для G, если все вершины в G зеленые и все вершины в ее окрестности N G (G) красные. Обратите внимание, что N G (G) имеет не более DK вершин, что D G (V) ≤ D для каждой вершины. Поэтому вероятность того, что случайный раздел является хорошим разделом для G - 2 - (D +1) K  и, таким образом, G является объединением некоторых зеленых компонентов. Чтобы найти максимальную вершину К-подграфа для хорошего раздела G, достаточно найти коллекцию H зеленых компонентов, таких, что общее число вершин Н и общее число ребер в H максимальна. С этой целью мы сначала вычислим в O (DN) время число Ni  вершин и  число Ni ребер внутри каждого компонента зеленого Ni. Затем мы находим коллекцию H зеленых компонентов, которая максимизирует при условии. Это может быть решено в O (кn) время с помощью  стандартного алгоритма динамического программирования для задачи о ранце .

Таким образом, с вероятностью по крайней мере 2 - (D +1) K , мы можем найти максимум K-вершин индуцированного подграфа графа G за O ((D + K) п) время. Используя методы Наора, Шульмана и  Сринивасана, мы получим повторное требуемое семейство разбиений размера 2 (Д +1) K (DK + K) O (Log (DK + K)) Log N, что может быть вычислено в линейное время. Затем получаем детерминированный алгоритм, который работает за O (F (K, D) N Log N) время, где F (K, D) = 2 (Д +1) K (DK + K) O (Log (DK + K)) (D + K), который является O (N Log N) при фиксированном к и d, и равномерным полином для параметра к и фиксированной d.

    2.2 Подграф изоморфный графу с ограниченной степенью

Хотя проблема изоморфизма подграфа W [1] для общих графов, мы можем использовать случайные разделения на соискание степени ограниченных графами, даже во взвешенном случае. Отметим, что следующая теорема в невесовом случае также следует из результата Seese и более общего результата из Фрика и Grohe.

Теорема 1:  Пусть G = (V, E, W), где W: V, E → R, есть взвешенный граф (Орграф), максимальной степени d и H произвольного K-вершинного графа (диграф). Если G содержит индуцированный (частично) подграф H, то для фиксированных к и d , он занимает O (N log N) время, чтобы найти максимальный (минимум) вес индуцированного (частично) H-подграфа в G.

Доказательство. Рассмотрим индуцированный подграф. Пусть Н* максимальный (минимум) вес индуцированного H-подграфа в G. Генерация случайного разбиения (V G , V R) из V с  вероятностью не менее 2 - (D +1) K . Каждая компонента связности H является зеленой компонентой. Для каждой компоненты связности Hi  из Н, мы находим максимальный (мин.) вес Hi  подграфа Hi * в GG , который занимает O (k!kdn) времени. Затем с вероятностью по крайней мере 2 -(D +1) K , максим. (миним.) вес в индуцированном H-подграфе в G, мы можем найти в O (N) ожидаемое время для фиксированных к и d. Мы дерандомизируем алгоритм с помощью (п, (d + 1) к) – универсальных множеств для получения детерминированного алгоритма, который работает в O (N log N) время при фиксированных к и d. Для частного случая подграфа, мы используем случайное разбиение на разделы края E в зеленые и красные края (EG , ER ). Пусть Н – максимальный (минимум) вес частичного H-подграфа в G. С вероятностью не менее 2 -KD  (заметим, что к вершины совпадают с не более чем KD краями). Ребра  в H зеленые и все другие края прилегающие к краям в H красные, т. е. каждая связная компонента H является зеленый компонентой  в G [EG]. Остальные аргументы так же, как в случае индуцированного подграфа опускаются.

    2.3 Взвешенные K-независимые множества в D-вырожденных графах

Пусть d – фиксированная константа, и G = (V, E, W) – это  d-взвешенный граф с W: V → R. Рассмотрим задачу нахождения максимального веса независимых K – наборов  в G, т. е. множество к взаимно несмежных вершин максимального общего веса. Проблема W [1] для общих графов,  тривиально разрешима для d-вырожденных графов с использованием случайных разделений. Первое, мы ориентируем края G так, чтобы исходящая степень каждой вершины не превосходила d , что легко сделать за O (DN) время. Затем мы генерируем случайное разбиение (VG , VR) из V. Вероятность того, что максимальный вес к-независимого набора V полностью внутри GG  и из окрестности каждой вершины V полностью находится в GR  не менее 2 - (D +1) K . Таким образом, с вероятностью по крайней мере 2 - (D +1) K , V состоит из раковин из G G,  и  К – раковин крупнейших весов в G G. Мы можем легко найти это за O (кn) время, и, таким образом, с вероятностью по крайней мере 2 - (D +1) K, можем найти максимальный  вес независимых K-множеств за  O ((D + K) п) время. Опять же, мы можем провести дерандомизацию с помощью алгоритма (N, (D +1) К) - универсальных множеств и  получить детерминированный алгоритм , который работает за O (N log N) время для фиксированных к и d.

         Замечание 2. Для фиксированных константы К и D, мы можем использовать случайные разделения для нахождения максимального веса K-индуцированного соответствия в D-вырожденных графах за O (N log N) время.

   Список использованной литературы

1. N. Alon, R. Yuster, and U. Zwick, Color-coding, J. ACM 42(4): 844-856, 1995.

2. S. Arnborg, J. Lagergren and D. Seese, Easy problems for tree-decomposable

graphs, J. Algorithms 12: 308-340, 1991.

3. H.L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput. 25: 1305-1317, 1996.

4. L. Cai, Parameterized complexity of cardinality constrained optimization problems, submitted to a special issue of The Computer Journal on parameterized complexity, 2006.

5. L. Cai, S.M. Chan and S.O. Chan, research notes, 2006.

6. J. Chen, I. Kanj, and W. Jia, Vertex cover: further observations and further im-

provements, J. Algorithms 41: 280-301, 2001.

7. B. Courcelle, The monadic second-order logic of graphs I: recognisable sets of finite graphs, Inform. Comput. 85(1): 12-75, 1990.

8. R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.

9. M. Frick and M. Grohe, Deciding first-order properties of locally tree-decomposable structures, J. of the ACM 48(6): 1184-1206, 2001.

10. J. Kleinberg and E. Tardos, Algorithm Design, Pearson, 2005.

11. M. Naor, L.J. Schulman, and A. Srinivasan, Splitters and near-optimal derandomization, Proc. 36th Annual Symp Foundations of Computer Science, pp. 182-191, 1995.

12. N. Robertson and P.D. Seymour, Graph minors XIII: the disjoint paths problem, J. Comb. Ther.(B) 63(1): 65-110, 1995.

13. J.P. Schmidt and A. Siegel, The spatial complexity of oblivious k-probe hash functions, SIAM J. Comp. 19: 775-786, 1990.

14. D. Seese, Linear time computable problems and first-order descriptions, Mathematical Structures in Computer Science 6(6): 505-526, 1996.