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

Минимальная триангуляция заключается в добавлении к произвольному неориентированному графу минимального набора дуг, такого, что в результате получается хордальный граф. Граф является хордальным, если любой цикл длины не менее 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).

       '''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>;

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

Для множества вершин <math>A \subset V</math> подграф G, порожденный A, соответствует <math>G[A] = (A, W) \; </math>, где <math>uv \in W \; </math>, если <math>u, v \in A \; </math> и <math>uv \in E \} \; </math>. Замкнутой окрестностью A является <math>N[A] = U \; </math>, где <math>u, v \in U \; </math> для каждой <math>uv \in E \; </math>, где <math>u \in A \} \; </math> и <math>N(A) = N[A] \mathcal{n} A \; </math>. A называется [[клика|кликой]], если G[A] является полным графом. Множество вершин <math>S \in V \; </math> называется [[разделитель вершин|разделителем вершин]], если <math>G[V \mathcal{n} S] \; </math> является несвязным; S называется [[минимальный разделитель|минимальным разделителем]] вершин, если существует пара вершин <math>a, b \in V \mathcal{n} S</math>, такая, что a и b содержатся в разных компонентах связности <math>G[V \mathcal{n} S] \; </math> и в одной и той же компоненте связности <math>G[V \mathcal{n} S'] \; </math> для любого <math>S' \in S</math>. Множество вершин <math>\Omega \subseteq V \; </math> является ''потенциально максимальной кликой'', если не существует компоненты связности <math>G[V \mathcal{n} \Omega]</math>, содержащей <math>\Omega \; </math> в своей окрестности, и для каждой пары вершин <math>u, v \in \Omega \; </math> имеется дуга uv или существует компонента связности <math>G[V \mathcal{n} Q] \; </math>, содержащая в своей окрестности одновременно u и v.

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

   '''if''' <math>E_{\bar H}(U \mathcal{n} N_H[u]) < \frac{2}{5} | \bar E (H)|</math> '''then''' пометить u как s-вершину (стоп-вершину);

         '''if''' <math>E_{\bar H}(U \mathcal{n} N_H[C_k \cup \{ u \} ]) \ge \frac{2}{5} | \bar E (H)|</math> '''then'''

Быстрая минимальная триангуляция, рис. 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).