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

Материал из WEGA
Перейти к навигации Перейти к поиску
мНет описания правки
 
(не показаны 33 промежуточные версии этого же участника)
Строка 4: Строка 4:
== Постановка задачи ==
== Постановка задачи ==


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


Пусть 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).


Минимальные триангуляции были впервые описаны в середине семидесятых, и с тех пор было предложено множество алгоритмов. Полный обзор алгоритмов и различные характеризации хордальных графов и минимальных триангуляций можно найти в работе Хеггернеса и коллег [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], который позволяет получить алгоритм с временем выполнения <math>o(n^3) \; </math>.


Алгоритм быстрой минимальной триангуляции FMT. Дано: произвольный граф G = (V, E). Требуется: найти минимальную триангуляцию G0 графа G.
Пусть Q1, Q2 и Q3 – пустые очереди; поместить G в Q1; G0 = G; repeat
Создать нулевую матрицу M со строкой для каждой вершины из V (столбцы будут добавлены позднее); while Q1 непусто do
Извлечь граф H = (U; D) из Q1;
Вызвать процедуру Algorithm Partition(H), возвращающую подмножество вершин A С U;
Поместить множество вершин A в Q3;
for каждой связной компоненты C из H[Un A] do
Добавить столбец в M, такой, что M(v, C) = 1 для всех вершин v 2 NH(C); if существует антидуга UV в H[NH[C]] с u 2 C then
Поместить HC = (NH[C]; DC) в Q2, где MV ^ DC если u 2 C и MV ^ D; Вычислить MMT;
Добавить к G0 дуги, обозначенные ненулевыми элементами MMT; while Q3 непусто do
Извлечь множество вершин A из Q3;
if G0[A] неполно then Поместить G0[A] в Q2; Поменять местами имена Q1 и Q2; until Q1 пусто


Быстрая минимальная триангуляция, рис. 1
'''Алгоритм быстрой минимальной триангуляции FMT.'''
Алгоритм быстрой минимальной триангуляции
 
'''Дано:''' произвольный граф G = (V, E).
 
'''Требуется:''' найти минимальную триангуляцию G' графа G.
 
Пусть <math>Q_1</math>, <math>Q_2</math> и <math>Q_3</math> – пустые очереди; поместить G в <math>Q_1</math>; G' = G;
 
'''repeat'''
 
  Создать нулевую матрицу M со строкой для каждой вершины из V (столбцы будут добавлены позднее);
 
  '''while''' <math>Q_1</math> непусто '''do'''
 
      Извлечь граф H = (U, D) из <math>Q_1</math>;
 
      Вызвать процедуру '''Algorithm Partition'''(H), возвращающую подмножество вершин <math>A \subset U</math>;
 
      Поместить множество вершин A в <math>Q_3</math>;
 
      '''for''' каждой связной компоненты C из <math>H[U \mathcal {n} A]</math> '''do'''
 
        Добавить столбец в M, такой, что M(v, C) = 1 для всех вершин <math>v \in N_H(C)</math>;
 
        '''if''' существует антиребро uv в <math>H[N_H[C]] \; </math>, такая, что <math>u \in C</math> '''then'''
 
            Поместить <math>H_C = (N_H[C], D_C) \; </math> в <math>Q_2</math>, где <math>uv \notin D_C \; </math>, если <math>u \in C</math> и <math>uv \notin D</math>;
 
  Вычислить <math>MM^T \; </math>;
 
  Добавить к G' ребра, обозначенные ненулевыми элементами <math>MM^T \; </math>;
 
  '''while''' <math>Q_3</math> непусто '''do'''
 
      Извлечь множество вершин A из <math>Q_3</math>;
 
      '''if''' G'[A] неполно '''then'''
 
        Поместить G'[A] в '''Q_2''';
 
  Поменять местами имена <math>Q_1</math> и <math>Q_2</math>;
 
'''until''' <math>Q_1</math> пусто
 
 
Рис. 1. Алгоритм быстрой минимальной триангуляции
 


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


Для множества вершин 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] определяет независимые задачи минимальной триангуляции.
Для множества вершин <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 \subset 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' \subset 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} \Omega] \; </math>, содержащая в своей окрестности одновременно u и v.
Этот рекурсивный алгоритм определяет дерево, корнем которого является входной граф G, а каждая компонента связности G[V n A] становится потомком корневой вершины, определяемой G. Этот процесс рекурсивно продолжается для каждой подзадачи, определяемой этими компонентами связности. Вершина H, являющаяся подзадачей алгоритма, находится на уровне i, если расстояние от H до корня дерева равно i. Заметим, что триангуляция всех подзадач одного и того же уровня может выполняться независимо. Пусть k – количество уровней. Если этот рекурсивный алгоритм может быть выполнен для каждого подграфа на каждом уровне за время O(f(n)), тогда общее время исполнения составит O(f(n) k).
 
Принимая во внимание результаты из [1] и [7], получаем следующий рекурсивный алгоритм минимальной триангуляции. Найти множество вершин A, являющееся либо минимальным разделителем, либо потенциально максимальной кликой. Дополнить G[A] до клики. Рекурсивным образом для каждой компоненты связности C из <math>G[V \mathcal{n} A] \; </math>, где <math>G[N[C]] \; </math> не является кликой, найти минимальную триангуляцию <math>G[N[C]] \; </math>. Важное свойство алгоритма заключается в том, что множество компонент связности <math>G[V \mathcal{n} A] \; </math> определяет независимые задачи минимальной триангуляции.
 
Этот рекурсивный алгоритм определяет дерево, корнем которого является входной граф 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>.
 
 
Вышеприведенный алгоритм быстрой минимальной триангуляции использует очереди для воплощения этого поуровневого подхода, а также матричное умножение для вычисления всех разделителей вершин на заданном уровне за время <math>O(n^{ \alpha} ) \; </math>, где <math>\alpha < 2,376 \; </math> [3]. В отличие от ранее описанного рекурсивного алгоритма, он использует подпрограмму разбиения, которая возвращает либо [[множество]] минимальных разделителей, либо потенциально максимальную клику.
 
 
'''Алгоритм разбиения Partition'''
 
'''Дано:''' граф H = (U, D) (подзадача, извлеченная из <math>Q_1</math>).
 
'''Требуется:''' найти подмножество A множества U, такое, что либо A = N[K] для некоторого связного H[K], либо A является потенциально максимальной кликой H (и G').
 
'''Часть I: определение P'''
 
Снять отметки со всех вершин H;  k = 1;
 
'''while''' существует непомеченная вершина u '''do'''
 
  '''if''' <math>E_{\bar H}(U \mathcal{n} N_H[u]) < \frac{2}{5} | \bar E (H)|</math> '''then'''
 
      пометить u как s-вершину (стоп-вершину);
 
  '''else'''
 
      <math>C_k = \{ u \} \; </math> ; пометить u как c-вершину (вершину компонента);
 
      '''while''' существует вершина <math>v \in N_H[C_k]</math>, непомеченная или помеченная как s-вершина '''do'''
 
        '''if''' <math>E_{\bar H}(U \mathcal{n} N_H[C_k \cup \{ v \} ]) \ge \frac{2}{5} | \bar E (H)|</math> '''then'''
 
            <math>C_k = C_k \cup \{ v \} \; </math>; пометить v как c-вершину (вершину компонента);
 
        '''else'''
 
            Пометить v как p-вершину (вершину потенциально максимальной клики); Ассоциировать v с <math>C_k \; </math>;
 
      k = k + 1;
 
P = множество всех p-вершин и s-вершин;
 
 
''Часть II: определение A''
 
'''if''' <math>H[U \mathcal{n} P] \; </math> содержит полную компоненту C '''then''' <math>A = N_H [C] \; </math>;


'''else if''' существуют две несмежные вершины u, v, такие, что u является s-вершиной, а v является s-вершиной или p-вершиной '''then''' <math>A = N_H [u] \; </math>;


Вышеприведенный алгоритм быстрой минимальной триангуляции использует очереди для воплощения этого поуровневого подхода, а также матричное умножение для вычисления всех разделителей вершин на заданном уровне за время O(na), где a < 2:376 [3]. В отличие от ранее описанного рекурсивного алгоритма, он использует подпрограмму разбиения, которая возвращает либо множество минимальных разделителей, либо потенциально максимальную клику.
'''else if''' существуют две несмежные p-вершины u и v, где u ассоциирована с <math>C_i \; </math>, а v ассоциирована с <math>C_j \; </math>, <math>u \notin N_H (C_j) \; </math> и <math>v \notin N_H (C_i) \; </math> '''then''' <math>A = N_H [C_i \cup \{ u \}] \; </math>;


'''else''' A = P;


Алгоритм разбиения Partition
Дано:      граф H = (U, D) (подзадача, извлеченная из Q1). Требуется:  найти подмножество A множества U, такое, что либо A = N[K] для некоторого связного H[K], либо A является потенциально максимальной кликой H (и G0).
Часть I: определение P
Снять отметки со всех вершин H;  k = 1;
while существует непомеченная вершина u do
if Тд(и n NH[U]) < ||£(H)| then пометить u как s-вершину (стоп-вершину); else
Ck = fug; пометить u как c-вершину (вершину компонента);
while существует вершина v 2 NH[ Q ], непомеченная или помеченная как s-вершина do
if Ta(U\NH[CkU{v}]) > f|£(H)| then
Ck = C U {v}; пометить v как c-вершину (вершину компонента); else
Пометить v как p-вершину (вершину потенциально максимальной клики); Ассоциировать v с Ck; k = k + 1; P = множество всех p-вершин и s-вершин;
Часть II: определение A
if H[U n P] содержит полную компоненту C then A = NH[C];
else if существуют две несмежные вершины u, v, такие, что u является s-вершиной, а v является s-вершиной или p-вершиной then A = NH [ u ];
else if существуют две несмежные p-вершины u и v, где u ассоциирована с C, а v ассоциирована с Cj, u 62 NH(CJ) и V 2 6NH(Ci) then A = NH[Ci[f u g];
else A = P;


Быстрая минимальная триангуляция, рис. 2
Рис. 2. Алгоритм разбиения. Пусть <math>\bar E_H = W \; </math>, где <math>uv \in W \; </math>, если <math>uv \notin D \; </math> – множество антиребер H. Определим <math>E_{\bar H}(S) \; </math> как сумму степеней в <math>\bar H = (U, \bar E) \; </math> вершин <math>S \subseteq U = V(H) \; </math>
Алгоритм разбиения. Пусть £(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 + ), где O() – время, необходимое для вычисления MMT. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антидуг исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает log4/5(n2) = 2log4/5(n), чем достигается время исполнения O(log n).
Несмотря на то, что все подзадачи на одном и том же уровне могут решаться независимо, у них могут быть общие вершины и ребра, но не антиребра (т.е. пары вершин, не являющиеся смежными). Поскольку процесс триангуляции включает в себя добавление ребер, число антиребер на каждом уровне снижается, и сумма числа антиребер для всех подзадач на одном и том же уровне не может превышать <math>n^2 \; </math>. Алгоритм разбиения на рис. 2 использует этот факт; он имеет время выполнения <math>O(n^2 - m) \; </math>, что в сумме для каждого уровня дает <math>O(n^2) \; </math>. Таким образом, каждый уровень алгоритма быстрой минимальной триангуляции, приведенного на рис. 1, может быть выполнен за время <math>O(n^2 + n^{ \alpha }) \; </math>, где <math>O(n^{ \alpha }) \; </math> – время, необходимое для вычисления <math>MM^T \; </math>. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антиребер исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает <math>log_{ \frac{4}{5} }(n^2) = 2 \; log_{ \frac{4}{5} }(n)</math>, чем достигается время выполнения <math>O(n^{ \alpha } log \; n)</math>.


== Применение ==
== Применение ==


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




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


== Открытые вопросы ==
== Открытые вопросы ==


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


== См. также ==
== См. также ==

Текущая версия от 14:18, 1 октября 2023

Ключевые слова и синонимы

Задача минимального заполнения

Постановка задачи

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

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


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


Алгоритм быстрой минимальной триангуляции FMT.

Дано: произвольный граф G = (V, E).

Требуется: найти минимальную триангуляцию G' графа G.

Пусть [math]\displaystyle{ Q_1 }[/math], [math]\displaystyle{ Q_2 }[/math] и [math]\displaystyle{ Q_3 }[/math] – пустые очереди; поместить G в [math]\displaystyle{ Q_1 }[/math]; G' = G;

repeat
  Создать нулевую матрицу M со строкой для каждой вершины из V (столбцы будут добавлены позднее);
  while [math]\displaystyle{ Q_1 }[/math] непусто do
     Извлечь граф H = (U, D) из [math]\displaystyle{ Q_1 }[/math];
     Вызвать процедуру Algorithm Partition(H), возвращающую подмножество вершин [math]\displaystyle{ A \subset U }[/math];
     Поместить множество вершин A в [math]\displaystyle{ Q_3 }[/math];
     for каждой связной компоненты C из [math]\displaystyle{ H[U \mathcal {n} A] }[/math] do
        Добавить столбец в M, такой, что M(v, C) = 1 для всех вершин [math]\displaystyle{ v \in N_H(C) }[/math];
        if существует антиребро uv в [math]\displaystyle{ H[N_H[C]] \;  }[/math], такая, что [math]\displaystyle{ u \in C }[/math] then
           Поместить [math]\displaystyle{ H_C = (N_H[C], D_C) \;  }[/math] в [math]\displaystyle{ Q_2 }[/math], где [math]\displaystyle{ uv \notin D_C \;  }[/math], если [math]\displaystyle{ u \in C }[/math] и [math]\displaystyle{ uv \notin D }[/math];
  Вычислить [math]\displaystyle{ MM^T \;  }[/math];
  Добавить к G' ребра, обозначенные ненулевыми элементами [math]\displaystyle{ MM^T \;  }[/math];
  while [math]\displaystyle{ Q_3 }[/math] непусто do
     Извлечь множество вершин A из [math]\displaystyle{ Q_3 }[/math];
     if G'[A] неполно then
        Поместить G'[A] в Q_2;
  Поменять местами имена [math]\displaystyle{ Q_1 }[/math] и [math]\displaystyle{ Q_2 }[/math];
until [math]\displaystyle{ Q_1 }[/math] пусто


Рис. 1. Алгоритм быстрой минимальной триангуляции


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

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

Принимая во внимание результаты из [1] и [7], получаем следующий рекурсивный алгоритм минимальной триангуляции. Найти множество вершин A, являющееся либо минимальным разделителем, либо потенциально максимальной кликой. Дополнить G[A] до клики. Рекурсивным образом для каждой компоненты связности C из [math]\displaystyle{ G[V \mathcal{n} A] \; }[/math], где [math]\displaystyle{ G[N[C]] \; }[/math] не является кликой, найти минимальную триангуляцию [math]\displaystyle{ G[N[C]] \; }[/math]. Важное свойство алгоритма заключается в том, что множество компонент связности [math]\displaystyle{ G[V \mathcal{n} A] \; }[/math] определяет независимые задачи минимальной триангуляции.

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


Вышеприведенный алгоритм быстрой минимальной триангуляции использует очереди для воплощения этого поуровневого подхода, а также матричное умножение для вычисления всех разделителей вершин на заданном уровне за время [math]\displaystyle{ O(n^{ \alpha} ) \; }[/math], где [math]\displaystyle{ \alpha \lt 2,376 \; }[/math] [3]. В отличие от ранее описанного рекурсивного алгоритма, он использует подпрограмму разбиения, которая возвращает либо множество минимальных разделителей, либо потенциально максимальную клику.


Алгоритм разбиения Partition

Дано: граф H = (U, D) (подзадача, извлеченная из [math]\displaystyle{ Q_1 }[/math]).

Требуется: найти подмножество A множества U, такое, что либо A = N[K] для некоторого связного H[K], либо A является потенциально максимальной кликой H (и G').

Часть I: определение P

Снять отметки со всех вершин H;   k = 1;
while существует непомеченная вершина u do
  if [math]\displaystyle{ E_{\bar H}(U \mathcal{n} N_H[u]) \lt  \frac{2}{5} | \bar E (H)| }[/math] then
     пометить u как s-вершину (стоп-вершину);
  else
     [math]\displaystyle{ C_k = \{ u \} \;  }[/math] ; пометить u как c-вершину (вершину компонента);
     while существует вершина [math]\displaystyle{ v \in N_H[C_k] }[/math], непомеченная или помеченная как s-вершина do
        if [math]\displaystyle{ E_{\bar H}(U \mathcal{n} N_H[C_k \cup \{ v \} ]) \ge \frac{2}{5} | \bar E (H)| }[/math] then
           [math]\displaystyle{ C_k = C_k \cup \{ v \} \;  }[/math]; пометить v как c-вершину (вершину компонента);
        else
           Пометить v как p-вершину (вершину потенциально максимальной клики); Ассоциировать v с [math]\displaystyle{ C_k \;  }[/math];
     k = k + 1;
P = множество всех p-вершин и s-вершин;


Часть II: определение A

if [math]\displaystyle{ H[U \mathcal{n} P] \;  }[/math] содержит полную компоненту C then [math]\displaystyle{ A = N_H [C] \;  }[/math];
else if существуют две несмежные вершины u, v, такие, что u является s-вершиной, а v является s-вершиной или p-вершиной then [math]\displaystyle{ A = N_H [u] \;  }[/math];
else if существуют две несмежные p-вершины u и v, где u ассоциирована с [math]\displaystyle{ C_i \;  }[/math], а v ассоциирована с [math]\displaystyle{ C_j \;  }[/math], [math]\displaystyle{ u \notin N_H (C_j) \;  }[/math] и [math]\displaystyle{ v \notin N_H (C_i) \;  }[/math] then [math]\displaystyle{ A = N_H [C_i \cup \{ u \}] \;  }[/math];
else A = P;


Рис. 2. Алгоритм разбиения. Пусть [math]\displaystyle{ \bar E_H = W \; }[/math], где [math]\displaystyle{ uv \in W \; }[/math], если [math]\displaystyle{ uv \notin D \; }[/math] – множество антиребер H. Определим [math]\displaystyle{ E_{\bar H}(S) \; }[/math] как сумму степеней в [math]\displaystyle{ \bar H = (U, \bar E) \; }[/math] вершин [math]\displaystyle{ S \subseteq U = V(H) \; }[/math]


Несмотря на то, что все подзадачи на одном и том же уровне могут решаться независимо, у них могут быть общие вершины и ребра, но не антиребра (т.е. пары вершин, не являющиеся смежными). Поскольку процесс триангуляции включает в себя добавление ребер, число антиребер на каждом уровне снижается, и сумма числа антиребер для всех подзадач на одном и том же уровне не может превышать [math]\displaystyle{ n^2 \; }[/math]. Алгоритм разбиения на рис. 2 использует этот факт; он имеет время выполнения [math]\displaystyle{ O(n^2 - m) \; }[/math], что в сумме для каждого уровня дает [math]\displaystyle{ O(n^2) \; }[/math]. Таким образом, каждый уровень алгоритма быстрой минимальной триангуляции, приведенного на рис. 1, может быть выполнен за время [math]\displaystyle{ O(n^2 + n^{ \alpha }) \; }[/math], где [math]\displaystyle{ O(n^{ \alpha }) \; }[/math] – время, необходимое для вычисления [math]\displaystyle{ MM^T \; }[/math]. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антиребер исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает [math]\displaystyle{ log_{ \frac{4}{5} }(n^2) = 2 \; log_{ \frac{4}{5} }(n) }[/math], чем достигается время выполнения [math]\displaystyle{ O(n^{ \alpha } log \; n) }[/math].

Применение

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


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

Открытые вопросы

Приведенный алгоритм позволяет найти минимальную триангуляцию за время [math]\displaystyle{ O((n^2 + n^{ \alpha }) log \; n) }[/math], где [math]\displaystyle{ O(n^{ \alpha }) \; }[/math] – время, необходимое для проведения бинарного матричного умножения [math]\displaystyle{ n \times n \; }[/math]. В результате любое улучшение алгоритма бинарного матричного умножения позволит повысить скорость алгоритма нахождения минимальной триангуляции. Интересный вопрос заключается в том, верно ли обратное: существует ли алгоритм бинарного матричного умножения с временем [math]\displaystyle{ O((n^2 + n^{ \beta })f(n)) \; }[/math], где [math]\displaystyle{ O(n^{ \beta }) \; }[/math] – время, необходимое для нахождения минимальной триангуляции, и [math]\displaystyle{ f(n) = o(n^{ \alpha -2}) \; }[/math] или по меньшей мере [math]\displaystyle{ f(n) = O(n) \; }[/math]. Более простой и релевантный вопрос был ранее задан в [8]: сложнее ли вычислить минимальную триангуляцию, чем определить, содержит ли граф хотя бы один треугольник? Более алгоритмический вопрос выглядит следующим образом: существует ли алгоритм нахождения минимальной триангуляции за время [math]\displaystyle{ O(n^2 + n^{ \alpha }) \; }[/math].

См. также

Литература

1. Bouchitte, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31, 212-232(2001)

2. Bouchitte, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1-2), 17-32 (2002)

3. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251-280 (1990)

4. Fomin, F.V., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in. In: ICALP of LNCS, vol. 3142, pp. 568-580. Springer, Berlin (2004)

5. Heggernes, P., Telle, J.A., Villanger, Y.: Computing minimal triangulations in time 0{nahgn) = o(n2:376). SIAM J. Discret. Math. 19(4), 900-913 (2005)

6. Huson, D.H., Nettles, S., Warnow, T.: Obtaining highly accurate topology estimates of evolutionary trees from very short sequences. In: RECOMB, 1999, pp. 198-207

7. Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theor. Comput. Sci. 175, 309-335(1997)

8. Kratsch, D., Spinrad, J.: Minimal fill in O(n2:69) time. Discret. Math. 306(3), 366-371 (2006)

9. Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discret. Appl. Math. 79, 171-188(1997)

10. Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5,146-160 (1976)