Алгоритм FKT

FKT (назван по именам Фишера, Кастеляйна и Темперли) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является #P-полной для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.

История

Задача подсчёта планарных совершенных паросочетаний берёт свои корни в статистической механике и химии, где первоначальным вопросом был: Если двухатомные молекулы абсорбируются на поверхности, образуя один слой, сколькими способами они могут быть расположены[1]? Статистическая сумма является важной величиной, которая кодирует статистические свойства системы в состоянии равновесия, и она могла бы быть использована для ответа на предыдущий вопрос. Однако попытка вычислить статистическую сумму исходя из определения мало практична. Тогда точное решение физической системы есть нахождение альтернативной формы статистической суммы для конкретной физической системы, которая достаточно просто вычислима точно[2]. В начале 1960-х определение точно решаемая задача не было строгим[3] и информатика дала точное определение с введением понятия полиномиального времени, которое датируется 1965-м годом. Аналогично, понятие не совсем решаемая задача должно соответствовать #P-трудности, которая была определена в 1979 году.

Другой тип физической системы для рассмотрения — комбинации димеров, соединений из двух атомов. Модель димера считает число покрытия димерами графа[4]. Ещё одна рассматриваемая система — связь молекул H2O в форме льда, что моделируется как ориентированный 3-регулярный граф, в котором ориентация рёбер в каждой вершине не может быть той же самой. Насколько много ориентаций рёбер эта модель имеет?

Заинтересовавшись физическими системами из димеров, в 1961-м году Кастеляйн[5], а также Темперли вместе с Фишером[6] независимо нашли число замощений костяшками домино для прямоугольника . Это эквивалентно подсчёту числа совершенных паросочетаний для решётки. В 1967 году Кастеляйн обобщил этот результат на все планарные графы[7][8].

Алгоритм

Подход

Главная идея — любой ненулевой член пфаффиана матрицы смежности графа G соответствует совершенному паросочетанию. Тогда, если можно найти ориентацию графа G, чтобы все знаки членов пфаффиана были одинаковы (не имеет значения, будут они со знаком + или -), тогда абсолютное значение пфаффиана равно числу совершенных паросочетаний графа G. Алгоритм FKT выполняет эту задачу для планарного графа G. Ориентация, которую алгоритм находит, называется пфаффовой ориентацией.

Пусть G=(V, E) будет неориентированной матрицей с матрицей смежности A. Определим PM(n) как множество разбиений n элементов на пары, тогда число совершенных паросочетаний в графе G равно

Тесно связан с этим пфаффиан для матрицы A

где sgn(M) — знак перестановки M. Пфаффова ориентация графа G — это ориентированный граф H с (1, −1, 0)-матрицей смежности B, такой что pf(B)=PerfMatch(G)[9]. В 1967 году Кастеляйн доказал, что планарные графы имеют эффективно вычисляемую пфаффову ориентацию. А именно для планарного графа G пусть H будет ориентированной версией графа G, в котором нечётное число рёбер ориентировано против часовой стрелки для любой грани планарного вложения графа G. Тогда H является пфаффовой ориентацией графа G.

Наконец, для любой кососимметричной матрицы A,

где det(A) является определителем матрицы A. Этот результат принадлежит Кэли[10]. Поскольку определители вычисляются эффективно, тоже верно и для PerfMatch(G).

Описание алгоритма
Пример, показывающий как алгоритм FKT находит пфаффову ориентацию.
  1. Вычисляем планарное вложение графа G.
  2. Вычисляем остовное дерево T1 входного дерева G.
  3. Даём произвольную ориентацию каждому ребру графа G, которое принадлежит также дереву T1.
  4. Используем планарное вложение, чтобы создать (неориентированный) граф T2, который имеет тот же набор вершин, что и двойственный граф графа G.
  5. Создаём ребро в T2 между двумя соответствующими гранями графа G, имеющими общее ребро в G, которое не принадлежит T1. (Заметим, что T2 — дерево.)
  6. Для каждого листа v в T2 (которое не является одновременно корнем):
    1. Пусть e — одиночное ребро графа G в грани, соответствующей v, которое ещё не получило ориентацию.
    2. Даём e ориентацию, такую что число рёбер, ориентированных по часовой стрелке нечётно.
    3. Удаляем v из T2.
  7. Возвращаем абсолютное значение пфаффиана (1, −1, 0)-матрицы смежности графа G, которое равно квадратному корню из определителя.

Обобщения

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

Теорема Понтрягина — Куратовского утверждает, что

конечный граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного K5 (полный граф с пятью вершинами) или K3,3 (полный двудольный граф с двумя долями размера три).

Виджай Вазирани обобщил алгоритм FKT на графы, которые не содержат подграф, гомеоморфный K3,3[11]. Поскольку подсчёт числа совершенных паросочетаний в графе общего вида является #P-полной задачей, требуются некоторые ограничения на входной граф если только сложность FP, функциональной версии P, не равна #P. Подсчёт паросочетаний, который известен также как индекс Хосойи, также является #P-полной задачей даже для планарных графов[12].

Приложения

Алгоритм FKT интенсивно используется в голографических алгоритмах на планарных графах через matchgates (двухкубитовые элементы Вэлианта)[3]. Например, рассмотрим плоскую версию модели льда, упомянутую выше, которая имеет техническое название #PL-3-NAE-SAT (здесь NAE означает «Not All Equal» = «не все равны»). Вэлиант нашёл алгоритм полиномиального времени для решения этой задачи, который использует matchgates[13].

Примечания
  1. Hayes, 2008.
  2. Baxter, 2008, с. 11.
  3. Cai, Lu, Xia, 2010.
  4. Kenyon, Okounkov, 2005, с. 342–343.
  5. Kasteleyn, 1961, с. 1209–1225.
  6. Temperley, Fisher, 1961, с. 1061–1063.
  7. Kasteleyn, 1963, с. 287–293.
  8. Kasteleyn, 1967, с. 43–110.
  9. Thomas, 2006, с. 963–984.
  10. Cayley, 1847, с. 93–96.
  11. Vazirani, 1989, с. 152—164.
  12. Jerrum, 1987, с. 121–134.
  13. Valiant, 2004, с. 306–315.

Литература
  • Rodney J. Baxter. Exactly Solved Models in Statistical Mechanics. — 3rd. — Dover Publications, 2008. — С. 11. — ISBN 978-0-486-46271-4. Год первого издания 1982
  • Brian Hayes (scientist). Accidental Algorithms // American Scientist. — 2008. — January–February.
  • Jin-Yi Cai, Pinyan Lu, Mingji Xia. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP // Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium. — Las Vegas, NV, USA: IEEE, 2010.
  • Richard Kenyon, Andrei Okounkov. What is a Dimer? // AMS. — 2005. — Т. 52, вып. 3.
  • Kasteleyn P. W. The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice // Physica. — 1961. — Т. 27, вып. 12. — doi:10.1016/0031-8914(61)90063-5. — .
  • Temperley H. N. V., Michael E. Fisher. Dimer problem in statistical mechanics-an exact result // Philosophical Magazine. — 1961. — Т. 6, вып. 68. — doi:10.1080/14786436108243366.
  • Kasteleyn P. W. Dimer Statistics and Phase Transitions // Journal of Mathematical Physics. — 1963. — Т. 4, вып. 2. — С. 287–293. — doi:10.1063/1.1703953. — .
  • Kasteleyn P. W. Graph theory and crystal physics // Graph Theory and Theoretical Physics / Frank Harary. — New York: Academic Press, 1967. — С. 43–110.
  • Robin Thomas. A survey of Pfaffian orientations of graphs // International Congress of Mathematicians. — Zurich: European Mathematical Society, 2006. — Т. III. — С. 963–984.
  • Arthur Cayley. Sur les determinants gauches // Crelle's Journal. — 1847. — Т. 38. — С. 93–96. Перевод заголовка: О косых определителях
  • Vijay Vazirani. NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems // Information and Computation. — 1989. — Т. 80, вып. 2. — С. 152—164. — ISSN 0890-5401. — doi:10.1016/0890-5401(89)90017-5.
  • Mark Jerrum. Two-dimensional monomer-dimer systems are computationally intractable // Journal of Statistical Physics. — 1987. — Т. 48, вып. 1. — С. 121–134. — doi:10.1007/BF01010403. — .
  • Leslie G. Valiant. Holographic Algorithms (Extended Abstract) // Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. — Rome, Italy: IEEE Computer Society, 2004. — С. 306–315. — ISBN 0-7695-2228-9. — doi:10.1109/FOCS.2004.34.

Ссылки
  • Больше информации об алгоритме, его истории и примерах можно найти в главе 2 и разделе 5.3.2 диссертации Дмитрия Каменецкого PhD thesis
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.