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

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

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

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

Минимальная триангуляция заключается в добавлении к произвольному неориентированному графу минимального набора дуг, такого, что в результате получается хордальный граф. Граф является хордальным, если любой цикл длины не менее 4 содержит дугу между двумя непоследовательными вершинами цикла. Пусть G = (V, E) – простой неориентированный граф, где n = jVj and m = jEj. Граф H = (v, E [ F), где E \ F = ;, представляет собой триангуляцию графа G, если H является хордальным; H представляет собой минимальную триангуляцию, если не существует F0 С F, такого, что H0 = (V;E [ F0) является хордальным. Дуги в F называются дополняющими дугами; триангуляция является минимальной в том и только том случае, если удаление любой дополняющей дуги приводит к появлению бесхордовых циклов из 4 вершин [10].

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

Алгоритм быстрой минимальной триангуляции 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 Алгоритм быстрой минимальной триангуляции

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

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

Алгоритм разбиения 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 Алгоритм разбиения. Пусть £(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).

См. также

• Древесная ширина графов

Литература

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)