TheFisher–Kasteleyn–Temperley (FKT)algorithm, named afterMichael Fisher,Pieter Kasteleyn, andNeville Temperley, counts the number ofperfect matchings in aplanar graph in polynomial time. This same task is#P-complete for general graphs. Formatchings that are not required to be perfect, counting them remains #P-complete even for planar graphs. The key idea of the FKT algorithm is to convert the problem into aPfaffian computation of askew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standarddeterminant algorithms.

The problem of counting planar perfect matchings has its roots instatistical mechanics andchemistry, where the original question was: Ifdiatomic molecules are adsorbed on a surface, forming a single layer, how many ways can they be arranged?^[1] Thepartition function is an important quantity that encodes the statistical properties of a system at equilibrium and can be used to answer the previous question. However, trying to compute the partition function from its definition is not practical. Thus to exactly solve a physical system is to find an alternate form of the partition function for that particular physical system that is sufficiently simple to calculate exactly.^[2] In the early 1960s, the definition ofexactly solvable was not rigorous.^[3] Computer science provided a rigorous definition with the introduction ofpolynomial time, which dates to 1965. Similarly, the notation of notexactly solvable, for acounting problem such as this one, should correspond to#P-hardness, which was defined in 1979.

Another type of physical system to consider is composed ofdimers, which is a polymer with two atoms. The dimer model counts the number of dimer coverings of a graph.^[4] Another physical system to consider is the bonding ofH₂O molecules in the form of ice. This can be modelled as a directed, 3-regular graph where the orientation of the edges at each vertex cannot all be the same. How many edge orientations does this model have?

Motivated by physical systems involving dimers, in 1961, Pieter Kasteleyn^[5] and Neville Temperley and Michael Fisher^[6] independently found the number ofdomino tilings for them-by-n rectangle. This is equivalent to counting the number of perfect matchings for them-by-nlattice graph. By 1967, Kasteleyn had generalized this result to all planar graphs.^[7][8]

The main insight is that every non-zero term in thePfaffian of theadjacency matrix of a graphG corresponds to a perfect matching. Thus, if one can find anorientation ofG to align all signs of the terms inPfaffian (no matter+ or- ), then the absolute value of thePfaffian is just the number of perfect matchings inG. The FKT algorithm does such a task for a planar graphG. The orientation it finds is called aPfaffian orientation.

LetG = (V,E) be an undirected graph withadjacency matrixA. DefinePM(n) to be the set of partitions ofn elements into pairs, then the number of perfect matchings inG is

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

Closely related to this is thePfaffian for ann byn matrixA

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

where sgn(M) is thesign of the permutationM. A Pfaffian orientation ofG is a directed graphH withadjacency matrixB such that pf(B) = PerfMatch(G).^[9] In 1967, Kasteleyn proved that planar graphs have an efficiently computable Pfaffian orientation. Specifically, for a planar graphG, letH be a directed version ofG where an odd number of edges are oriented clockwise for every face in a planar embedding ofG. ThenH is a Pfaffian orientation ofG.

Finally, for anyskew-symmetric matrixA,

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

where det(A) is thedeterminant ofA. This result is due toArthur Cayley.^[10] Sincedeterminants are efficiently computable, so is PerfMatch(G).

1. Compute a planarembedding ofG.
2. Compute aspanning treeT₁ of the input graphG.
3. Give an arbitrary orientation to each edge inG that is also inT₁.
4. Use the planar embedding to create an (undirected) graphT₂ with the same vertex set as thedual graph ofG.
5. Create an edge inT₂ between two vertices if their corresponding faces inG share an edge inG that is not inT₁. (Note thatT₂ is a tree.)
6. For each leafv inT₂ (that is not also the root):
   1. Lete be the lone edge ofG in the face corresponding tov that does not yet have an orientation.
   2. Givee an orientation such that the number of edges oriented clock-wise is odd.
   3. Removev fromT₂.
7. Return the absolute value of thePfaffian of theadjacency matrix ofG, which is the square root of the determinant.

The sum of weighted perfect matchings can also be computed by using theTutte matrix for the adjacency matrix in the last step.

Kuratowski's theorem states that

afinite graph is planarif and only if it contains nosubgraphhomeomorphic toK₅ (complete graph on five vertices) orK_3,3 (complete bipartite graph on two partitions of size three).

Vijay Vazirani generalized the FKT algorithm to graphs that do not contain a subgraph homeomorphic toK_3,3.^[11] More generally the complexity of counting perfect matchings has been completely characterized for families of graphs that are closed undergraph minors. There exists a family of graphs, theshallow vortex grids, such that for a minor-closed family that does not include all shallow vortex grids, this counting problem is polynomially solvable. But for a minor-closed family that includes all shallow vortex grids, such as the${\displaystyle K_8}$-minor-free graphs, the problem of counting perfect matchings is#P-complete.^[12]Since counting the number of perfect matchings in a general graph is also #P-complete, some restriction on the input graph is required unlessFP, the function version ofP, is equal to#P. Counting matchings, which is known as theHosoya index, is also #P-complete even for planar graphs.^[13]

The FKT algorithm has seen extensive use inholographic algorithms on planar graphs viamatchgates.^[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"). Valiant found a polynomial time algorithm for this problem which uses matchgates.^[14]

• More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky'sPhD thesis

• Graph algorithms
• Planar graphs

• Articles with short description
• Short description matches Wikidata