El algoritmo Fisher–Kasteleyn–Temperley ( FKT ) , llamado así por Michael Fisher , Pieter Kasteleyn y Neville Temperley , cuenta el número de emparejamientos perfectos en un grafo planar en tiempo polinomial. Esta misma tarea es #P-completa para grafos generales. Para los emparejamientos que no se requiere que sean perfectos, contarlos sigue siendo #P-completo incluso para grafos planares. La idea clave del algoritmo FKT es convertir el problema en un cálculo Pfaffiano de una matriz antisimétrica derivada de una incrustación planar del grafo. El Pfaffiano de esta matriz se calcula luego de manera eficiente utilizando algoritmos determinantes estándar .
El problema de contar emparejamientos perfectos planares tiene sus raíces en la mecánica estadística y la química , donde la pregunta original era: si las moléculas diatómicas se adsorben en una superficie, formando una sola capa, ¿de cuántas formas se pueden organizar? [1] La función de partición es una cantidad importante que codifica las propiedades estadísticas de un sistema en equilibrio y se puede utilizar para responder la pregunta anterior. Sin embargo, tratar de calcular la función de partición a partir de su definición no es práctico. Por lo tanto, resolver exactamente un sistema físico es encontrar una forma alternativa de la función de partición para ese sistema físico en particular que sea lo suficientemente simple como para calcularlo exactamente. [2] A principios de la década de 1960, la definición de exactamente solucionable no era rigurosa. [3] La ciencia de la computación proporcionó una definición rigurosa con la introducción del tiempo polinomial , que data de 1965. De manera similar, la notación de no exactamente solucionable , para un problema de conteo como este, debería corresponder a #P-dureza , que se definió en 1979.
Otro tipo de sistema físico a considerar está compuesto por dímeros , que es un polímero con dos átomos. El modelo de dímeros cuenta el número de recubrimientos de dímeros de un grafo. [4] Otro sistema físico a considerar es el enlace de moléculas de H 2 O en forma de hielo. Esto se puede modelar como un grafo regular dirigido, 3- donde la orientación de los bordes en cada vértice no puede ser la misma. ¿Cuántas orientaciones de borde tiene este modelo?
Motivados por los sistemas físicos que involucran dímeros, en 1961, Pieter Kasteleyn [5] y Neville Temperley y Michael Fisher [6] encontraron de forma independiente el número de teselas de dominó para el rectángulo m por n . Esto es equivalente a contar el número de coincidencias perfectas para el gráfico reticular m por n . En 1967, Kasteleyn había generalizado este resultado a todos los gráficos planares. [7] [8]
La idea principal es que cada término distinto de cero en el Pfaffian de la matriz de adyacencia de un grafo G corresponde a una correspondencia perfecta. Por lo tanto, si uno puede encontrar una orientación de G para alinear todos los signos de los términos en Pfaffian (sin importar + o - ), entonces el valor absoluto del Pfaffian es simplemente el número de correspondencias perfectas en G . El algoritmo FKT realiza tal tarea para un grafo plano G . La orientación que encuentra se llama orientación Pfaffian .
Sea G = ( V , E ) un grafo no dirigido con matriz de adyacencia A . Defina PM ( n ) como el conjunto de particiones de n elementos en pares, entonces el número de emparejamientos perfectos en G es
Estrechamente relacionado con esto está el Pfaffian para una matriz n por n A
donde sgn( M ) es el signo de la permutación M . Una orientación Pfaffiana de G es un grafo dirigido H con matriz de adyacencia B tal que pf( B ) = PerfMatch( G ). [9] En 1967, Kasteleyn demostró que los grafos planares tienen una orientación Pfaffiana computable de manera eficiente. Específicamente, para un grafo planar G , sea H una versión dirigida de G donde un número impar de aristas están orientadas en el sentido de las agujas del reloj para cada cara en una incrustación plana de G . Entonces H es una orientación Pfaffiana de G .
Finalmente, para cualquier matriz antisimétrica A ,
donde det( A ) es el determinante de A . Este resultado se debe a Arthur Cayley . [10] Dado que los determinantes son eficientemente computables, también lo es PerfMatch( G ).
La suma de las coincidencias perfectas ponderadas también se puede calcular utilizando la matriz de Tutte para la matriz de adyacencia en el último paso.
El teorema de Kuratowski establece que
Vijay Vazirani generalizó el algoritmo FKT a los grafos que no contienen un subgrafo homeomorfo a K 3,3 . [11] De manera más general, la complejidad de contar emparejamientos perfectos se ha caracterizado completamente para familias de grafos que están cerrados bajo los menores de grafo . Existe una familia de grafos, las rejillas de vórtices poco profundos , de modo que para una familia cerrada con menores que no incluye todas las rejillas de vórtices poco profundos, este problema de conteo es polinomialmente solucionable. Pero para una familia cerrada con menores que incluye todas las rejillas de vórtices poco profundos, como los grafos sin menores, el problema de contar emparejamientos perfectos es #P-completo . [12] Dado que contar el número de emparejamientos perfectos en un grafo general también es #P-completo, se requiere alguna restricción en el grafo de entrada a menos que FP , la versión de función de P , sea igual a #P . El conteo de emparejamientos, que se conoce como el índice de Hosoya , también es #P-completo incluso para grafos planares. [13]
El algoritmo FKT se ha utilizado ampliamente en algoritmos holográficos en gráficos planares mediante puertas de coincidencia. [3] Por ejemplo, considere la versión plana del modelo de hielo mencionado anteriormente, que tiene el nombre técnico # PL -3-NAE- SAT (donde NAE significa "no todos iguales"). Valiant encontró un algoritmo de tiempo polinomial para este problema que utiliza puertas de coincidencia. [14]
