Алгоритм ФКТ

Алгоритм подсчета идеальных паросочетаний в плоских графах

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

История

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

Другой тип физической системы, который следует рассмотреть, состоит из димеров , которые представляют собой полимер с двумя атомами. Димерная модель подсчитывает количество димерных покрытий графа. ^[4] Другая физическая система, которую следует рассмотреть, — это связь молекул H ₂ O в форме льда. Его можно смоделировать как ориентированный 3- регулярный граф, в котором ориентация ребер в каждой вершине не может быть одинаковой. Сколько ориентаций ребер имеет эта модель?

Вдохновленные физическими системами, включающими димеры, в 1961 году Питер Кастелейн ^[5] , Невилл Темперли и Майкл Фишер ^[6] независимо друг от друга нашли количество разбиений домино для прямоугольника m - n . Это эквивалентно подсчету количества идеальных паросочетаний для решетчатого графа размером mxn . К 1967 году Кастелейн обобщил этот результат на все плоские графы. ^{[7] [8]}

Алгоритм

Объяснение

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

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

${\displaystyle \operatorname {PerfMatch} (G)=\sum _{M\in PM(|V|)}\prod _{(i,j)\in M}A_{ij}.}$

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

${\displaystyle \operatorname {pf} (A)=\sum _{M\in PM(n)}\operatorname {sgn} (M)\prod _{(i,j)\in M}A_{ij},}$

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

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

${\displaystyle \operatorname {pf} (A)^{2}=\det(A),}$

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

Описание высокого уровня

Пример, показывающий, как алгоритм FKT находит ориентацию Пфаффа.

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

Обобщения

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

Теорема Куратовского утверждает, что

конечный граф является планарным тогда и только тогда, когда он не содержит подграфа, гомеоморфного K 5 ₍ полный граф на пяти вершинах) или K _3,3 ( полный двудольный граф на двух разбиениях размера три).

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

Приложения

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

Рекомендации

1. Хейс, Брайан (январь – февраль 2008 г.), «Случайные алгоритмы», американский ученый
2. Бакстер, Р.Дж. (2008) [1982]. Точно решаемые модели в статистической механике (Третье изд.). Дуврские публикации. п. 11. ISBN 978-0-486-46271-4.
3. Цай, Джин-И; Лу, Пиньян; Ся, Минджи (2010). Голографические алгоритмы со спичечными воротами фиксируют точно управляемую плоскую #CSP . Основы компьютерных наук (FOCS), 2010 г., 51-й ежегодный симпозиум IEEE. Лас-Вегас, Невада, США: IEEE. arXiv : 1008.0683 . Бибкод : 2010arXiv1008.0683C.
4. Кеньон, Ричард; Окуньков, Андрей (2005). «Что такое димер?» (PDF) . АМС . 52 (3): 342–343.
5. Кастелейн, П.В. (1961), «Статистика димеров на решетке. I. Число расположений димеров на квадратичной решетке», Physica , 27 (12): 1209–1225, Бибкод : 1961Phy....27.1209K , дои : 10.1016/0031-8914(61)90063-5
6. Темперли, HNV ; Фишер, Майкл Э. (1961). «Задача о димерах в статистической механике - точный результат». Философский журнал . 6 (68): 1061–1063. Бибкод : 1961PMag....6.1061T. дои : 10.1080/14786436108243366.
7. Кастелейн, PW (1963). «Статистика димеров и фазовые переходы». Журнал математической физики . 4 (2): 287–293. Бибкод : 1963JMP.....4..287K. дои : 10.1063/1.1703953.
8. Кастелейн, П.В. (1967), «Теория графов и физика кристаллов», в Харари, Ф. (ред.), Теория графов и теоретическая физика , Нью-Йорк: Academic Press, стр. 43–110.
9. Томас, Робин (2006). Обзор пфаффовых ориентаций графов (PDF) . Международный конгресс математиков. Том. III. Цюрих: Европейское математическое общество. стр. 963–984.
10. Кэли, Артур (1847). «Sur les determinants gauches» [О перекосе определителей]. Журнал Крелля . 38 : 93–96.
11. Вазирани, Виджай В. (1989). «NC-алгоритмы для вычисления количества совершенных паросочетаний в графах, свободных от K3,3, и связанные с ними проблемы». Информация и вычисления . 80 (2): 152–164. дои : 10.1016/0890-5401(89)90017-5 . HDL : 1813/6700 . ISSN  0890-5401.
12. Джеррам, Марк (1987), «Двумерные мономер-димерные системы вычислительно трудноразрешимы», Journal of Statistical Physics , 48 ​​(1): 121–134, Бибкод : 1987JSP....48..121J, doi : 10.1007 /BF01010403, S2CID  189854401.
13. Валиант, Лесли Г. (2008). «Голографические алгоритмы» (PDF) . SIAM Journal по вычислительной технике . 37 (5): 1565–1594. дои : 10.1137/070682575. МР  2386281.

Внешние ссылки

• Более подробную историю, информацию и примеры можно найти в главе 2 и разделе 5.3.2 кандидатской диссертации Дмитрия Каменецкого.