HOME

TheInfoList



OR:

The FKT algorithm, named after
Fisher Fisher is an archaic term for a fisherman, revived as gender-neutral. Fisher, Fishers or The Fisher may also refer to: Places Australia *Division of Fisher, an electoral district in the Australian House of Representatives, in Queensland *Elect ...
, Kasteleyn, and
Temperley Temperley is a district in Greater Buenos Aires, Argentina, located in the south of Lomas de Zamora Partido. History In 1854 the industrial and textile merchant George Temperley (born in 1823 in Newcastle upon Tyne, England) bought from the M ...
, counts the number of
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
s in a
planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...
graph in polynomial time. This same task is #P-complete for general graphs. For matchings 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 a
Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
computation of a
skew-symmetric matrix In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition In terms of the entries of the matrix, if a_ ...
derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms.


History

The problem of counting planar perfect matchings has its roots in
statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
and
chemistry Chemistry is the science, scientific study of the properties and behavior of matter. It is a natural science that covers the Chemical element, elements that make up matter to the chemical compound, compounds made of atoms, molecules and ions ...
, where the original question was: If
diatomic molecule Diatomic molecules () are molecules composed of only two atoms, of the same or different chemical elements. If a diatomic molecule consists of two atoms of the same element, such as hydrogen () or oxygen (), then it is said to be homonuclear. Ot ...
s are adsorbed on a surface, forming a single layer, how many ways can they be arranged? 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. 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. In the early 1960s, the definition of ''exactly solvable'' was not rigorous. Computer science provided a rigorous definition with the introduction of
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, which dates to 1965. Similarly, the notation of not ''exactly solvable'', for a counting problem such as this one, should correspond to #P-hardness, which was defined in 1979. Another type of physical system to consider is composed of dimers, which is a polymer with two atoms. The dimer model counts the number of dimer coverings of a graph. Another physical system to consider is the bonding of H2O 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, Kasteleyn and Temperley and Fisher independently found the number of domino tilings for the ''m''-by-''n'' rectangle. This is equivalent to counting the number of perfect matchings for the ''m''-by-''n''
lattice graph In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a latti ...
. By 1967, Kasteleyn had generalized this result to all planar graphs.


Algorithm


Explanation

The main insight is that every non-zero term in the
Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
of the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
of a graph ''G'' corresponds to a perfect matching. Thus, if one can find an
orientation Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building de ...
of ''G'' to align all signs of the terms in
Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
(no matter ''+'' or ''-'' ), then the absolute value of the
Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
is just the number of perfect matchings in ''G''. The FKT algorithm does such a task for a planar graph ''G''. The orientation it finds is called a
Pfaffian orientation In graph theory, a Pfaffian orientation of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction. When a graph has a Pfaffian orientation, the orientati ...
. Let ''G'' = (''V'', ''E'') be an undirected graph with
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
''A''. Define ''PM''(''n'') to be the set of partitions of ''n'' elements into pairs, then the number of perfecting matchings in ''G'' is :\operatorname(G) = \sum_ \prod_ A_. Closely related to this is the
Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
for an ''n'' by ''n'' matrix ''A'' :\operatorname(A) = \sum_ \operatorname(M) \prod_ A_, where sgn(''M'') is the sign of the permutation ''M''. A Pfaffian orientation of ''G'' is a directed graph ''H'' with
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
''B'' such that pf(''B'') = PerfMatch(''G''). In 1967, Kasteleyn proved that planar graphs have an efficiently computable Pfaffian orientation. Specifically, for a planar graph ''G'', let ''H'' be a directed version of ''G'' where an odd number of edges are oriented clockwise for every face in a planar embedding of ''G''. Then ''H'' is a Pfaffian orientation of ''G''. Finally, for any
skew-symmetric matrix In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition In terms of the entries of the matrix, if a_ ...
''A'', :\operatorname(A)^2 = \det(A), where det(''A'') is the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of ''A''. This result is due to Cayley. Since
determinants In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
are efficiently computable, so is PerfMatch(''G'').


High-level description

# Compute a planar
embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is gi ...
of ''G''. # Compute a
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
''T''1 of the input graph ''G''. # Give an arbitrary orientation to each edge in ''G'' that is also in ''T''1. # Use the planar embedding to create an (undirected) graph ''T''2 with the same vertex set as the
dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
of ''G''. # Create an edge in ''T''2 between two vertices if their corresponding faces in ''G'' share an edge in ''G'' that is not in ''T''1. (Note that ''T''2 is a tree.) # For each leaf ''v'' in ''T''2 (that is not also the root): ## Let ''e'' be the lone edge of ''G'' in the face corresponding to ''v'' that does not yet have an orientation. ## Give ''e'' an orientation such that the number of edges oriented clock-wise is odd. ## Remove ''v'' from ''T''2. # Return the absolute value of the
Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
of the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
of ''G'', which is the square root of the determinant.


Generalizations

The sum of weighted perfect matchings can also be computed by using the
Tutte matrix In graph theory, the Tutte matrix ''A'' of a graph ''G'' = (''V'', ''E'') is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the set of vert ...
for the adjacency matrix in the last step.
Kuratowski's theorem In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdi ...
states that : a
finite graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a Set (mathematics), set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstra ...
is planar
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
it contains no subgraph
homeomorphic In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphi ...
to ''K''5 (
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
on five vertices) or ''K''3,3 (
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...
on two partitions of size three).
Vijay Vazirani Vijay Virkumar Vazirani ( hi, विजय वीरकुमार वज़ीरानी; b. 1957) is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the Universi ...
generalized the FKT algorithm to graphs that do not contain a subgraph homeomorphic to ''K''3,3. Since counting the number of perfect matchings in a general graph is #P-complete, some restriction on the input graph is required unless FP, the function version of P, is equal to #P. Counting matchings, which is known as the
Hosoya index The Hosoya index, also known as the Z index, of a graph is the total number of matchings in it. The Hosoya index is always at least one, because the empty set of edges is counted as a matching for this purpose. Equivalently, the Hosoya index is ...
, is also #P-complete even for planar graphs.


Applications

The FKT algorithm has seen extensive use in
holographic algorithm In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains un ...
s on planar graphs via matchgates. For example, consider the planar version of the ice model mentioned above, which has the technical name # PL-3-NAE-
SAT The SAT ( ) is a standardized test widely used for college admissions in the United States. Since its debut in 1926, its name and scoring have changed several times; originally called the Scholastic Aptitude Test, it was later called the Schol ...
(where NAE stands for "not all equal"). Valiant found a polynomial time algorithm for this problem which uses matchgates.


References

{{reflist


External links

*More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky'
PhD thesis
Graph algorithms Planar graphs