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

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

 

Рассматривается NP-трудная задача нахождения наибольшей клики графа (MaximumCliqueProblem, MCP). Предлагается двухфазный алгоритм нахождения точного решения MCP для разреженного графа. Первая фаза алгоритма — предобработка входного графа путем разложения его на атомы, а вторая фаза — применение к каждому атому классического алгоритма Уилфа и формирование решения для графа в целом. Уровень разреженности графа задается в виде ограничения на его древовидную ширину. Показано, что время выполнения предлагаемого алгоритма полиномиально зависит от числа вершин и экспоненциально от древовидной ширины графа. Это позволяет применять данный алгоритм к графам большой размерности и малой древовидной ширины.

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

 

Задача о наибольшей клике (англ. вариант − Maximum Clique Problem, или коротко MCP) является одной из известных NP-трудных задач дискретной математики и теории сложности вычислений. Эта задача имеет разнообразные приложения. В современных приложениях, таких как структурных анализ химических соединений и геномных баз данных, автоматизация проектирования сложных технических изделий и систем, кластеризация данных, поиск наибольших клик приходится осуществлять в разреженных графах очень большой размерности [1, 2, 8]. Исследуемые графы могут содержать до миллиона вершин. Вследствие этого востребованы эффективные алгоритмы, позволяющие находить точное решение MCP за приемлемое время в классе таких графов.

В данной работе предлагается двухфазный алгоритм нахождения точного решения MCP, первая фаза которого — предобработка входного графа путем разложения его на атомы, а вторая фаза — применение к каждому атому классического алгоритма Уилфа [14] и формирование решения для графа в целом. Уровень разреженности входного графа задается в виде ограничения на его древовидную ширину и предположения о наличии в графе кликовых минимальных сепараторов. В работе показано, что время выполнения предлагаемого алгоритма полиномиально зависит от числа вершин и экспоненциально от древовидной ширины входного графа, что позволяет его применять для обработки графов большой размерности с малой древовидной шириной. В работе используются основные понятия и обозначения, принятые в [10]. Для простоты изложения рассматриваются только связные обыкновенные графы, т. е. конечные, неориентированные без петель и кратных ребер графы, состоящие из одной компоненты связности.

1. Формулировка задачи

Рассмотрим связный обыкновенный графG = (V, E) с множеством вершин V и множеством ребер E, при этом n = |V | ≥ 2, |E | ≥ 1. Множество всех вершин графа G, смежных с некоторой вершиной v∈V, образует в графе G окрестность N(v) этой вершины, а множество N [v] = N(v) ∪∪{v} − замкнутую окрестность. Граф G′ = (V′, E′) называется подграфом графа G = (V, E) при условии, что V′ ⊆V, E′ ⊆E. Если множество вершин подграфа G′ есть V′, а множество ребер E′ совпадает с множеством всех ребер графаG, оба конца которых принадлежат V′, то G′ = (V′, E′) называется подграфом, порожденным множеством V′, и обозначается черезG(V′).

Множество вершин V V образует клику графа G = (V, E), когда любые две входящие в него вершины смежны в G, т. е. подграф G(V′) полный. Клика называется максимальной, если она не содержится в клике с большим количеством вершин, и наибольшей, если число вершин в ней наибольшее среди всех клик. Размер наибольшей клики графаG обозначается ϕ(G) и называется кликовым числом графа G. Множество вершин V V независимое в G, если любые две входящие в него вершины не смежны, т. е. подграф G(V) безреберный. Независимое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности независимое множество называется наибольшим. Мощность наибольшего независимого множества вершин графа G называется числом независимости и обозначается через α0(G).

Понятия клики и независимого множества являются антиподами в том смысле, что всякая клика (максимальная, наибольшая) графа G является независимым множеством (максимальным, наибольшим) в дополнительном графеи, следовательно, ϕ(G) = α0

Распознавательный вариант MCP традиционно формулируется следующим образом.

УСЛОВИЕ. Заданы граф G = (V, E) и целое число 0 ≤ L≤ n.

ВОПРОС. Существует ли в G клика размера не менее L?

Аналогичным образом формулируется распознавательный вариант задачи о наибольшем независимом множестве (англ. вариант − Maximum Independent Set Problem, или коротко MISP). Заметим, что для графа G всегда , где , и переход к дополнению n-вершинного графа осуществим за время O(n2). Таким образом, задачи MCP и MISP полиномиально сводимы друг к другу и в этом смысле эквивалентны. Как известно, обе эти задачи в распознавательной формулировке являются NP-полными и для них пока не найдено полиномиальных по времени разрешающих алгоритмов [9]. Далее в статье рассматриваются оптимизационные варианты данных задач, в которых требуется для заданного связного обыкновенного графа найти наибольшую клику (наибольшее независимое множество).

2. Основные классические алгоритмы решения

Для нахождения точного решения задач MCP и MISP существует большое число алгоритмов, время выполнения которых экспоненциально зависит от числа вершин и ребер входного графа.Наиболее известными из них являются алгоритм Брона-Кербоша и алгоритм Уилфа. Алгоритм Брона−Кербоша является рекурсивной процедурой, которая последовательно наращивает кандидатскую клику [3]. Время работы алгоритма Брона−Кербоша составляет

O(poly(n)∙ 3n/ 3) = O(poly(n)∙ 1,4422n), (1)

где poly(n) — некоторый полином от числа вершин входного графа. Поскольку граф с n вершинами может содержать до 3n/ 3 максимальных клик [10], то алгоритм Брона−Кербоша сопоставим по трудоемкости с процедурой полного перебора. Известны различные модификации данного алгоритма [12]. Самая быстрая из них находит точное решение MCP за время

O(poly(n)∙ 20,249n) = O(poly(n)∙ 1,1888n).

В отличие от алгоритма Брона−Кербоша рекурсивный алгоритм Уилфа [14] предназначен для нахождения точного решения задачи MISP. Суть его состоит в следующем. Для любой произвольно выбранной вершины v∈V графа G = (V,E) существуют два виданезависимых множеств: те, которые включают вершину v и те, которые не включают данную вершину. Исходя из этого, исходную задачу можно расщепить на две подзадачи (как уменьшенные копии исходной) соответственно двум случаям:

‒                    формируемое независимое множество содержит выбранную вершину v. В данной ситуации все вершины из N(v) уже не могут входить в это независимое множество, и дальнейшее его наращивание надо осуществлять в графе G(V\ N [v]) = G — N [v];

‒                    формируемое независимое множество не содержитвершину v. Дальнейшее наращивание этого множества следует продолжать в графе G(V\ {v}) = G — v.

Обозначим через maxset(G) функцию, которая возвращает мощность наибольшего независимого множества n-вершинного графа G, а черезT(n) время ее выполнения. Тогда общая схема рекурсивного алгоритма расщепления для нахождения решения MISP описывается равенством

maxset(G) = max{maxset(G − v), 1 + maxset(G — N [v])},

а оценка времени его работы вычисляется из неоднородного линейного рекуррентного соотношения с постоянными коэффициентами

T(n) = T(n — 1) +T(n — 2) + f(n), (2)

где f(n) — некоторая функция полиномиального порядка роста. Соотношение (2) справедливо, поскольку граф G — v содержит в точности n — 1 вершин, а граф G — N [v] может иметь до n — 2 вершин (исключается сама вершина v и хотя бы одна из смежных с ней вершин). Применение к (2) техники Кульмана−Люкхардта [7] приводит к оценке

T(n) = O(poly(n)∙ 1,619n),

которая несколько хуже оценки (1). Однако если усовершенствовать правило выбора вершины v, по которой выполняется расщепление в maxset(G), например, выбирать вершину степени 3, то приходим к рекуррентному соотношению

T(n) = T(n — 1) + T(n — 4) + poly(n)

иоценке

T(n) = O(poly(n)∙ 1,39n), (3)

которая уже лучше (1).

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

3. Декомпозиция, сохраняющая клики графа

Вначале введем необходимые понятия. Пусть G= (V, E), n = |V | ≥ 2, |E | ≥ 1 — связный обыкновенный граф. Под атомом графа G= (V, E) понимается его максимальный относительно включения связный подграф, не имеющий кликовых минимальных сепараторов. Говорят, что множество вершин S⊆V разделяет две несмежные вершины x и y графа G, если в подграфе G(V\ S) вершины x и y принадлежат различным компонентам связности. Множество S при этом называется (x,y)-сепаратором и минимальным (x,y)-сепаратором, если никакое его собственное подмножество не является (x,y)-сепаратором. СепараторS считается минимальным, если в графе G существует хотя бы одна такая пара вершин x и y, чтоS − минимальный (x,y)-сепаратор. Минимальный сепаратор S называется кликовым, если S образует клику в G.

Идея разложение графа на атомы была предложена Тарьяном [13] еще в 1985 г. как средство реализации подхода «разделяй и властвуй» для решения оптимизационных задач. Тарьяном было установлено, что атомарное разложение не разрушает кликиграфа и не порождает новых клик. Позднее в работе [11] было доказано, что атомарное разложение уникальнодля всякого графа, если его осуществлять только кликовыми минимальными сепараторами. В настоящее время атомарное разложение особенно востребовано современными приложениями, базирующимися на теоретико-графовых моделях большой размерности. Поэтому актуально создание новых и усовершенствование известных полиномиальных алгоритмов, осуществляющих такое разложение.

Разложение графа G на атомы сводится к многократному его разделению на части одним из найденных кликовых минимальных сепараторов S, выделением компонент связности графа G(V\ S) и копированием S в эти компоненты. Этот процесс продолжается до тех пор, пока в полученных частях не окажется кликовых минимальных сепараторов. Алгоритм атомарного разложения представлен в работе [6]. Данный алгоритм позволяет за время O(n3) найти для графа G= (V, E) множество его кликовых минимальных сепараторов Δ(G) и множество атомов Ω(G). Важно отметить, что пара (G), (G) — это компактное описание всякого графа большой размерности с сохранением его внутренней структуры. Это описание может быть предварительно создано и хранится во внешней памяти компьютера, а необходимые для обработки атомы последовательно загружаться в оперативную память. Возможна организация параллельных и распределенных вычислений путем одновременной обработки нескольких атомов.

Установлены важные свойства атомарного разложения [11, 13]:

1)                 всякий атом из (G) является порожденным подграфом графа G;

2)                 множество (G) всегда сохраняет все клики графа G, т. е. всякая клика графа G становится кликой одного из его атомов, и новых клик при разложении не возникает;

3)                 1 ≤ |Ω(G)| ≤n, т. е. количество атомов в Ω(G) не превосходит числа вершин графаG;

4)                 для разреженного графа G — графа с ограниченной (значениемk) древовидной шириной − число вершин каждого атома ограничено сверху некоторой положительной целой константой kn.

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

4. Характеризация разреженных графов

Известно несколько формальных определений разреженного графа. Связный граф G = (V, E),n = |V | ≥ 2, |E | ≥ 1, называют (реберно) разреженным, если число его ребер удовлетворяет условию

|E| ≤ anb, (4)

где a  0, 1 ≤ b  2 − положительные вещественные константы и n= |V|. Считают, чем меньше значение b, тем более разреженным является граф G. Для сравнения, в каждом дереве число ребер равноn — 1, т. е. b = 1, что отвечает нижней границе значения b, а для любого полного n-вершинного графа всегда |E| = n(n — 1) /2, т. е. b = 2, что соотвествует верхней границе значения b.

Существует другое определение разреженного графа, которое выражается через числовой параметрtw(G), называемый древовидной шириной графа [4]. Для tw(G)верны границы: 1 ≤ tw(G) ≤ n — 1. Так, всякое n-вершинное дерево (n ≥ 2) имеет единичную древовидную ширину, что отвечает нижней границе для tw(G), а полному n-вершинному графу свойственна древовидная ширина, равная n — 1, что соответствует верхней границе для tw(G). Пусть k есть некоторая заданная положительная целая константа. Если tw(G) ≤ k, то говорят, что графG= (V, E) обладаетограниченной (значением k) древовидной шириной. Считается, чем меньше значение k, тем более разреженным является граф G. Известно [4], что если tw(G) ≤ k, то для числа ребер графа G= (V, E) справедливо неравенство

|E| ≤kn — k(k+ 1)/2. (5)

При k = 1 и k = n — 1 соотношение (5) приводит к неравенствам (4), отвечающим деревьям и полным графам. Следовательно, ограничение tw(G) ≤ k не противоречит (4) и задает естественную меру разреженности графа G. Учитывая, что всегда ϕ(G) — 1 ≤ tw(G), можно говорить о том, что значение tw(G) ограничивает также размеры клик графа G.

5. Описание двухфазного алгоритма и оценка его вычислительной сложности

Нахождение точного решения MCP применительно к разреженному связному графу G= (V, E), n = |V | ≥ 2, |E | ≥ 1,для которогоtw(G) ≤ k, сводится к выполнению двух фаз.

Фаза 1. Для графа G построить атомарное представление (G).

Фаза 2. Применить последовательно алгоритм maxset ко всем атомам из множества Ω(G). Предварительно для каждого атома выполнить переход к его дополнению. Сформировать решение для графа G на основе полученных результатов: наибольшую клику определить как наибольшую по мощности среди всех найденных в атомах максимальных клик. В качестве результата выдать наибольшую клику графа G и ее мощность.

Время выполнения фазы1 составляет O(n3). Принимая во внимание свойства атомов, приведенные выше, и оценку (3) получаем, что время решения задачи, применительно к отдельному атому, составляет

O(poly(k) ⋅1,39k),

а для графа G в целом

O(n⋅poly(k) ⋅1,39k). (6)

Из оценки (6) следует, что время работы двухфазного алгоритма полиномиально зависит от n и экспоненциально от k. Следовательно, чем более разреженным является входной граф, тем быстрее работает данный алгоритм. Алгоритмы с оценками вида (6) принято называть FPT(FixedParameterTractable)-алгоритмами [5]. Существование такого алгоритма для MCP и MISP свидетельствует о том, что эти задачи FPT-разрешимы относительно древовидной ширины графа.

Заключение

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

 

Литература:

 

1.      Boginski V., Butenko S. and Pardalos P. M. Mining market data: a network approach // Computers & Operations Research. 2006. 33. P. 3171−3184.
2.      Broder A., Kumar R., Maghoul F., Raghavan P., Rajagopalan S., Stata R., Tomkins A. and Wiener J. Graph structure in the Web // J. Computer Networks.2000. 33. P. 309–320.
3.      Bron C. and Kerbosch J. Algorithm 457: finding all cliques of an undirected graph // J. Communications of the ACM. 1973. 16(9). P. 575–577.
4.      Bykova V. V. Computational aspects of treewidth for graph // J. Applied Discrete Math. 2011. 3(13). P. 65−79 (in Russian)
5.      Bykova V. V. FPT-algorithms on graphs of limited treewidth. // J. Applied Discrete Math. 2012. 2(16). P. 65−78 (in Russian)
6.      Bykova V. V. The Clique Minimal Separator Decomposition of a Hypergraph // J. of Siberian Federal University. Mathematics  Physics. 2012. 1(5). P. 36–45 (in Russian)
7.      Bykova V. V. On the asymptotic solution of the recurrence relations of special type and the technology Kullmann−Luckhardt // J. Applied Discrete Math. 2013. 4(22). P. 56−66 (in Russian)
8.      Gardiner E., Willett P., Artymiuk P. and Gardiner E. Graph-theoretic techniques for macromolecular docking // J. Chem. Inf. Comput. 2000. 40. P. 273–279.
9.      Garey M. and Johnson D. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman andCompany, New York, 1979.
10. Emelichev V. A. et al. Lectures on the theoryof graphs. Moscow. Book House Librokom, 2012 (in Russian)
11. Leimer H. G. Optimal decomposition by clique separators // J. Discrete Math. 1993. 113. P. 99–123.
12. Robson J. M. Algorithms for maximum independent sets // J. Algorithms. 1986. 7(3). P. 425–440.
13. Tarjan R. E. Decomposition by clique separators // J. Discrete Math. 1985. 55. P. 221–232.
14. Wilf H. S. Algorithms and complexity. NJ. Prentice-Hall. Englewood Cliffs, 1986.