FKT algorithm

The Fisher–Kasteleyn–Temperley (FKT) algorithm, named after Michael Fisher, Pieter Kasteleyn, and Neville Temperley, counts the number of perfect matchings in a planar graph in polynomial time.

The key idea of the FKT algorithm is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph.

The problem of counting planar perfect matchings has its roots in statistical mechanics and chemistry, where the original question was: If diatomic molecules are adsorbed on a surface, forming a single layer, how many ways can they be arranged?

[1] The partition function is an important quantity that encodes the statistical properties of a system at equilibrium and can be used to answer the previous question.

Motivated by physical systems involving dimers, in 1961, Pieter Kasteleyn[5] and Neville Temperley and Michael Fisher[6] independently found the number of domino tilings for the m-by-n rectangle.

[7][8] The main insight is that every non-zero term in the Pfaffian of the adjacency matrix of a graph G corresponds to a perfect matching.

Kuratowski's theorem states that Vijay Vazirani generalized the FKT algorithm to graphs that do not contain a subgraph homeomorphic to K3,3.

[3] For example, consider the planar version of the ice model mentioned above, which has the technical name #PL-3-NAE-SAT (where NAE stands for "not all equal").