FKT algorithm

The Fisher–Kasteleyn–Temperley algorithm, or FKT algorithm, is a mathematical method for counting perfect matchings. A perfect matching occurs when every vertex in a graph is paired with exactly one partner through an edge. This task is incredibly difficult for most types of graphs. In computer science, counting these matchings in general graphs is classified as #P-complete. This means the problem is computationally very hard. However, the FKT algorithm can solve this problem in polynomial time for planar graphs. A planar graph is a graph that can be drawn on a flat surface without any edges crossing each other.

To understand how the algorithm works, we must look at its mechanism. The core idea involves converting the counting problem into a Pfaffian computation. This computation uses a skew-symmetric matrix, which is a special type of square matrix. The algorithm begins by finding a planar embedding of the graph. It then seeks a specific way to direct the edges, known as a Pfaffian orientation. In this orientation, the signs of the terms in the Pfaffian align correctly. Once this orientation is found, the absolute value of the Pfaffian equals the number of perfect matchings. The Pfaffian itself can be calculated efficiently by finding the square root of the determinant of the matrix.

Finding this Pfaffian orientation follows a specific sequence of steps. First, the algorithm computes a planar embedding of the graph. Next, it identifies a spanning tree, which is a subgraph that connects all vertices without forming any loops. The algorithm gives an arbitrary orientation to the edges within this tree. It then uses the planar embedding to create a second tree, T2, based on the dual graph. The vertices of T2 correspond to the faces of the original graph. For each leaf in this new tree, the algorithm orients the remaining edges so that an odd number of edges are oriented clockwise around each face. This specific arrangement ensures the orientation is a Pfaffian orientation.

The history of this algorithm is rooted in the fields of statistical mechanics and chemistry. Scientists were interested in how diatomic molecules, called dimers, arrange themselves on a surface. They wanted to know how many ways these molecules could form a single layer. This question is related to finding the partition function, which describes the statistical properties of a system at equilibrium. In 1961, Pieter Kasteleyn, Neville Temperley, and Michael Fisher independently discovered how to count domino tilings in an m-by-n rectangle. This was equivalent to counting perfect matchings in an m-by-n lattice graph. By 1967, Kasteleyn expanded this work to include all planar graphs.

Mathematical rigor evolved alongside these discoveries. In the early 1960s, the term "exactly solvable" was not yet strictly defined. Computer science provided clarity in 1965 with the introduction of polynomial time. Later, in 1979, the concept of #P-hardness was defined to describe problems that are not easily solvable. The FKT algorithm is significant because it moves a problem from the realm of the impossible to the realm of the efficient. While counting matchings in general graphs remains #P-complete, the FKT algorithm provides a fast solution for the planar subset. This distinction is vital for researchers working with large-scale physical models.

There are several notable variations and generalizations of this work. For instance, the algorithm can be used to compute the sum of weighted perfect matchings by using a Tutte matrix. Researchers have also looked at graphs that are nearly planar. Vijay Vazirani generalized the algorithm to graphs that do not contain a specific type of subgraph known as K3,3. The complexity of these problems is often tied to graph minors. For example, counting perfect matchings is solvable in polynomial time for certain minor-closed families of graphs. However, if a family includes all shallow vortex grids, the problem becomes #P-complete again.

The FKT algorithm connects deep mathematical theory to practical scientific models. It has been used in holographic algorithms through the use of matchgates. One specific application involves the ice model, technically known as #PL-3-NAE-SAT. This model describes the bonding of H2O molecules in the form of ice. In this model, the system is represented as a directed, 3-regular graph. The algorithm helps determine how many ways these molecules can orient their edges. By bridging the gap between graph theory and physical chemistry, the FKT algorithm remains a fundamental tool in modern science.