Алгоритм ФКТ
Алгоритм Фишера-Кастелейна-Темперли ( FKT ) Майкла , названный в честь Фишера , Питера Кастелейна и Невилла Темперли , подсчитывает количество идеальных паросочетаний в плоском графе за полиномиальное время. Эта же задача является #P-полной для общих графов. Для паросочетаний , которые не обязаны быть идеальными, их подсчет остается #P-полным даже для плоских графов. Основная идея алгоритма FKT состоит в том, чтобы преобразовать задачу в пфаффовское вычисление кососимметричной матрицы, полученной в результате плоского вложения графа. Затем пфаффиан этой матрицы эффективно вычисляется с использованием стандартных детерминантных алгоритмов .
История
[ редактировать ]Проблема подсчета плоских идеальных паросочетаний уходит корнями в статистическую механику и химию , где первоначальный вопрос заключался в следующем: если двухатомные молекулы адсорбируются на поверхности, образуя один слой, сколькими способами они могут располагаться? [1] Статистическая сумма — важная величина, которая кодирует статистические свойства системы в равновесии и может использоваться для ответа на предыдущий вопрос. Однако пытаться вычислить статистическую сумму по ее определению непрактично. Таким образом, чтобы точно решить физическую систему, нужно найти альтернативную форму статистической суммы для этой конкретной физической системы, которую достаточно просто вычислить точно. [2] В начале 1960-х годов определение точно решаемой задачи не было строгим. [3] Информатика предоставила строгое определение с введением полиномиального времени , которое датируется 1965 годом. Аналогичным образом, обозначение «не совсем разрешимо » для задачи счета такой должно соответствовать #P-hardness , которое было определено в 1979 году.
Другой тип физической системы, который следует рассмотреть, состоит из димеров , которые представляют собой полимеры с двумя атомами. Димерная модель подсчитывает количество димерных покрытий графа. [4] Другая физическая система, которую следует рассмотреть, — это связь молекул H 2 O в форме льда. Его можно смоделировать как ориентированный 3- регулярный граф, в котором ориентация ребер в каждой вершине не может быть одинаковой. Сколько ориентаций ребер имеет эта модель?
Вдохновленный физическими системами, включающими димеры, в 1961 году Питер Кастелейн [5] и Невилл Темперли и Майкл Фишер [6] независимо нашел количество плиток домино для mxn размером прямоугольника . Это эквивалентно подсчету количества идеальных паросочетаний для mxn размером решетчатого графа . К 1967 году Кастелейн обобщил этот результат на все плоские графы. [7] [8]
Алгоритм
[ редактировать ]Объяснение
[ редактировать ]Основная идея заключается в том, что каждый ненулевой член в пфаффиане матрицы смежности графа G соответствует идеальному паросочетанию. Таким образом, если можно найти ориентацию G , чтобы выровнять все знаки терминов в пфаффиане (неважно + или - ), то абсолютное значение пфаффиана - это просто количество идеальных паросочетаний в G . решает такую задачу для планарного графа G. Алгоритм FKT Ориентация, которую он находит, называется ориентацией Пфаффа .
Пусть G = ( V , E неориентированный граф с матрицей смежности A. ) — Определим PM ( n ) как набор разбиений n элементов на пары, тогда количество идеальных паросочетаний в G будет равно
С этим тесно связан пфаффиан для матрицы n на n размера A.
где sn( M ) — знак перестановки M . Пфаффова ориентация графа G — это ориентированный граф H с матрицей смежности B такой, что pf( B ) = PerfMatch( G ). [9] В 1967 году Кастелейн доказал, что плоские графы имеют эффективно вычислимую пфаффову ориентацию. В частности, для планарного графа G пусть H будет ориентированной версией G , где нечетное количество ребер ориентировано по часовой стрелке для каждой грани в плоском вложении G . Тогда H — пфаффова ориентация G. группы
Наконец, для любой кососимметричной A матрицы
det( A ) — определитель A где . Этот результат принадлежит Артуру Кэли . [10] Поскольку определители эффективно вычислимы, то и PerfMatch( G ) тоже.
Описание высокого уровня
[ редактировать ]
- плоское вложение G Вычислите .
- Вычислите остовное дерево T 1 входного графа G .
- Придайте произвольную ориентацию каждому ребру в G , которое также находится в T 1 .
- Используйте планарное вложение, чтобы создать (неориентированный) граф T 2 с тем же набором вершин, что и граф G двойственный .
- Создайте ребро в T 2 между двумя вершинами, если их соответствующие грани в G имеют общее ребро в G , которого нет в T 1 . (Обратите внимание, что T 2 — дерево.)
- Для каждого листа v в T 2 (который не является также корнем):
- Пусть e — единственное ребро G на грани, соответствующей v , которая еще не имеет ориентации.
- Придайте e такую ориентацию, чтобы число ребер, ориентированных по часовой стрелке, было нечетным.
- Удалите v из T 2 .
- Возвратите абсолютное значение пфаффиана матрицы смежности G , которое является квадратным корнем определителя.
Обобщения
[ редактировать ]Сумма взвешенных идеальных паросочетаний также может быть вычислена с использованием матрицы Тутте для матрицы смежности на последнем этапе.
Теорема Куратовского утверждает, что
- конечный граф планарен тогда и только тогда, когда содержит подграфа, гомеоморфного K он не 5 ( полный граф на пяти вершинах) или K 3,3 ( полный двудольный граф на двух разбиениях размера три).
Виджей Вазирани обобщил алгоритм FKT на графы, которые не содержат подграфа, гомеоморфного K 3,3 . [11] Поскольку подсчет количества идеальных паросочетаний в общем графе #P-полный , требуются некоторые ограничения на входной граф, если только FP , функциональная версия P , не равна #P . Подсчет паросочетаний, известный как индекс Хосоя , также является #P-полным даже для плоских графов. [12]
Приложения
[ редактировать ]Алгоритм FKT нашел широкое применение в голографических алгоритмах на плоских графах через matchgates . [3] Например, рассмотрим упомянутую выше планарную версию ледяной модели, имеющую техническое название # PL -3-NAE- SAT (где NAE означает «не все равны»). Valiant нашел для этой задачи алгоритм с полиномиальным временем, который использует matchgates. [13]
Ссылки
[ редактировать ]- ^ Хейс, Брайан (январь – февраль 2008 г.), «Случайные алгоритмы» , американский ученый.
- ^ Бакстер, Р.Дж. (2008) [1982]. Точно решаемые модели в статистической механике (Третье изд.). Дуврские публикации. п. 11. ISBN 978-0-486-46271-4 .
- ^ Jump up to: Перейти обратно: а б Цай, Джин-И; Лу, Пиньян; Ся, Минджи (2010). Голографические алгоритмы со спичечными воротами фиксируют точно управляемую плоскую #CSP . Основы компьютерных наук (FOCS), 2010 г., 51-й ежегодный симпозиум IEEE по . Лас-Вегас, Невада, США: IEEE. arXiv : 1008.0683 . Бибкод : 2010arXiv1008.0683C .
- ^ Кеньон, Ричард; Окуньков, Андрей (2005). «Что такое димер?» (PDF) . АМС . 52 (3): 342–343.
- ^ Кастелейн, П.В. (1961), «Статистика димеров на решетке. I. Число расположений димеров на квадратичной решетке», Physica , 27 (12): 1209–1225, Бибкод : 1961Phy....27.1209K , дои : 10.1016/0031-8914(61)90063-5
- ^ Темперли, HNV ; Фишер, Майкл Э. (1961). «Задача о димерах в статистической механике – точный результат». Философский журнал . 6 (68): 1061–1063. Бибкод : 1961PMag....6.1061T . дои : 10.1080/14786436108243366 .
- ^ Кастелейн, PW (1963). «Статистика димеров и фазовые переходы». Журнал математической физики . 4 (2): 287–293. Бибкод : 1963JMP.....4..287K . дои : 10.1063/1.1703953 .
- ^ Кастелейн, П.В. (1967), «Теория графов и физика кристаллов», в Харари, Ф. (ред.), Теория графов и теоретическая физика , Нью-Йорк: Academic Press, стр. 43–110.
- ^ Томас, Робин (2006). Обзор пфаффовых ориентаций графов (PDF) . Международный конгресс математиков . Том. III. Цюрих: Европейское математическое общество. стр. 963–984.
- ^ Кэли, Артур (1847). «О перекосах определителей». Журнал Крелля . 38 : 93–96.
- ^ Вазирани, Виджай В. (1989). «NC-алгоритмы вычисления числа совершенных паросочетаний в K 3,3- свободных графах и связанные с ними проблемы» . Информация и вычисления . 80 (2): 152–164. дои : 10.1016/0890-5401(89)90017-5 . HDL : 1813/6700 . ISSN 0890-5401 .
- ^ Джеррум, Марк (1987), «Двумерные системы мономер-димер вычислительно неразрешимы», Journal of Statistical Physics , 48 (1): 121–134, Bibcode : 1987JSP....48..121J , doi : 10.1007/ БФ01010403 , S2CID 189854401 .
- ^ Валиант, Лесли Г. (2008). «Голографические алгоритмы» (PDF) . SIAM Journal по вычислительной технике . 37 (5): 1565–1594. дои : 10.1137/070682575 . МР 2386281 .
Внешние ссылки
[ редактировать ]- Более подробную историю, информацию и примеры можно найти в главе 2 и разделе 5.3.2 кандидатской диссертации Дмитрия Каменецкого.