Быстрая минимальная триангуляция: различия между версиями

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

Пусть G = (V, E) – простой неориентированный граф, где <math>n = |V| \; </math> и <math>m = |E| \; </math>. Граф <math>H = (V, E \cup F) \; </math>, где <math>E \cap F = \empty \;</math>, представляет собой триангуляцию графа G, если H является хордальным; H представляет собой минимальную триангуляцию, если не существует <math>F' \subset F \; </math>, такого, что <math>H' = (V, E \cup F') \; </math> является хордальным. Дуги в F называются дополняющими дугами; триангуляция является минимальной в том и только том случае, если удаление любой дополняющей дуги приводит к появлению бесхордовых циклов из 4 вершин [10].

Минимальные триангуляции были впервые описаны в середине семидесятых, и с тех пор было предложено множество алгоритмов. Полный обзор алгоритмов и различные характеризации хордальных графов и минимальных триангуляций можно найти в работе Хеггернеса и коллег [5], посвященной минимальным триангуляциям. Алгоритмы минимальных триангуляций можно грубо разделить на алгоритмы, получающие триангуляцию посредством упорядочивания удалений, и алгоритмы, получающие ее при помощи разделителей вершин. Большинство этих алгоритмов имеют время исполнения <math>O(nm) \; </math>, что для плотных графов превращается в <math>O(n^3) \; </math>. Среди алгоритмов, использующих упорядочение удалений, самым быстрым на данный момент является алгоритм Кратча и Спинрада с временем исполнения <math>O(n^{2,69}) \; </math> [8]. Из алгоритмов, использующих разделители вершин, самым быстрым является алгоритм Хеггернеса и коллег [5] с временем исполнения <math>o(n^{2,376}) \; </math>, [5]. подробнее описанный ниже. И алгоритм Кратча и Спинрада [8], и алгоритм Хеггернеса и коллег используют алгоритм матричного умножения Копперсмита и Винограда [3], который позволяет получить алгоритм с временем исполнения o(n3).

'''repeat'''

       Вызвать процедуру '''Algorithm Partition'''(H), возвращающую подмножество вершин <math>A \subset U \; </math>;

       '''for''' каждой связной компоненты C из H[U\A] '''do'''

         '''if''' существует антидуга uv в <math>H[N_H[C]] \; </math>, такая, что <math>u \in C</math> '''then'''

   Добавить к G' дуги, обозначенные ненулевыми элементами <math>MM^T \; </math>;

       Извлечь множество вершин <math>A из Q_3</math>;

      '''if''' G'[A] неполно '''then''' Поместить G'[A] в '''Q_2''';

'''until''' <math>Q_1</math> пусто

Для множества вершин A С V подграф G, порожденный A, соответствует G[A] = (A, W), где uv 2 W, если u, v 2 A и uv e g. Замкнутой окрестностью A является N[A] = U, где u, v 2 U для каждой uv 2 E, где u 2 Ag и N(A) = N[A] n A. A называется кликой, если G[A] является полным графом. Множество вершин S С V называется разделителем вершин, если G[V n S] является несвязным; S называется минимальным разделителем вершин, если существует пара вершин a, b 2 VnS, такая, что a и b содержатся в разных компонентах связности G[V n S] и в одной и той же компоненте связности G[V n S0] для любого S0 С S. Множество вершин Q С V является потенциально максимальной кликой, если не существует компоненты связности G[V n Q], содержащей Q в своей окрестности, и для каждой пары вершин u, v 2 Q имеется дуга uv или существует компонента связности G[V n Q], содержащая в своей окрестности одновременно u и v. Принимая во внимание результаты из [1] и [7], получаем следующий рекурсивный алгоритм минимальной триангуляции. Найти множество вершин A, являющееся либо минимальным разделителем, либо потенциально максимальной кликой. Дополнить G[A] до клики. Рекурсивным образом для каждой компоненты связности C из G[V n A], где G[N[C]] не является кликой, найти минимальную триангуляцию G[N[C]]. Важное свойство алгоритма заключается в том, что множество компонент связности G[VnA] определяет независимые задачи минимальной триангуляции.

Этот рекурсивный алгоритм определяет дерево, корнем которого является входной граф G, а каждая компонента связности G[V n A] становится потомком корневой вершины, определяемой G. Этот процесс рекурсивно продолжается для каждой подзадачи, определяемой этими компонентами связности. Вершина H, являющаяся подзадачей алгоритма, находится на уровне i, если расстояние от H до корня дерева равно i. Заметим, что триангуляция всех подзадач одного и того же уровня может выполняться независимо. Пусть k – количество уровней. Если этот рекурсивный алгоритм может быть выполнен для каждого подграфа на каждом уровне за время O(f(n)), тогда общее время исполнения составит O(f(n) ■ k).

Вышеприведенный алгоритм быстрой минимальной триангуляции использует очереди для воплощения этого поуровневого подхода, а также матричное умножение для вычисления всех разделителей вершин на заданном уровне за время O(na), где a < 2:376 [3]. В отличие от ранее описанного рекурсивного алгоритма, он использует подпрограмму разбиения, которая возвращает либо множество минимальных разделителей, либо потенциально максимальную клику.

Быстрая минимальная триангуляция, рис. 2

Алгоритм разбиения. Пусть £(H) = W, где uv 2 W\fuv & D, – множество антидуг H. Определим £/j(S) как сумму степеней H = (U, Ё) вершин S с U = V(H)

Несмотря на то, что все подзадачи на одном и том же уровне могут решаться независимо, у них могут быть общие вершины и дуги, но не антидуги (т.е. пары вершин, не являющиеся смежными). Поскольку процесс триангуляции включает в себя добавление дуг, число антидуг на каждом уровне снижается, и сумма числа антидуг для всех подзадач на одном и том же уровне не может превышать n2. Алгоритм разбиения на рис. 2 использует этот факт; он имеет время исполнения O(n2 _ m), что в сумме для каждого уровня дает O(n2). Таким образом, каждый уровень алгоритма быстрой минимальной триангуляции, приведенного на рис. 1, может быть выполнен за время O(n2 + n˛), где O(n˛) – время, необходимое для вычисления MMT. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антидуг исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает log4/5(n2) = 2log4/5(n), чем достигается время исполнения O(n˛ log n).

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

Возможно, из-за связи с первоначальной задачей первые алгоритмы минимальной триангуляции были основаны на упорядочении и давали в результате порядок, называемый минимальным порядком удаления. С тех пор задача нахождения минимальной триангуляции получила широкое распространение; были опубликованы несколько новых вариантов применения и характеризаций, касающихся свойств разделителей вершин. В числе таких новых вариантов применения – нахождение древесной ширины графа и реконструкция эволюционной истории при помощи филогенетических деревьев [6]. Новые характеризации минимальной триангуляции на основе разделителей вершин повысили уровень знаний о минимальных триангуляциях [1,7,9]. Одним из результатов, основанных на этих характеризациях, является алгоритм вычисления древесной ширины графа за полиномиальное время в случае, когда количество минимальных разделителей полиномиально ограничено [2]. Другим вариантом применения являются более быстрые точные алгоритмы вычисления древесной ширины графа с полиномиальным временем исполнения [4].

Приведенный алгоритм позволяет найти минимальную триангуляцию за время O((n2 + и") log n), где O(n˛) – время, необходимое для проведения бинарного матричного умножения n х n. В результате любое улучшение алгоритма бинарного матричного умножения позволит повысить скорость алгоритма нахождения минимальной триангуляции. Интересный вопрос заключается в том, верно ли обратное: существует ли алгоритм бинарного матричного умножения с временем O((n2 + n^)f(n)), где O(n˛) – время, необходимое для нахождения минимальной триангуляции и f(n) = о{па~2) или по меньшей мере f(n) = O(n). Более простой и релевантный вопрос был ранее задан в [8]: сложнее ли вычислить минимальную триангуляцию, чем определить, содержит ли граф хотя бы один треугольник? Более алгоритмический вопрос выглядит следующим образом: существует ли алгоритм нахождения минимальной триангуляции за время O(n2 + na).