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

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

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

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

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