FKT algorithm

The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. Counting the number of matchings, even for planar graphs, is also #P-complete. The key idea is to convert the problem into a Pfaffian computation of a skew-symmetric matrix 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 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. 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 of exactly solvable was not rigorous.[3] Computer science provided a rigorous definition with the introduction of polynomial time, which dates to 1965. Similarly, the notation of not exactly solvable 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.[4] 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[5] and Temperley and Fisher[6] 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. By 1967, Kasteleyn had generalized this result to all planar graphs.[7][8]

Algorithm

Explanation

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. Thus, if one can find an orientation of G to align all signs of the terms in Pfaffian (no matter + or - ), then the absolute value of the Pfaffian is just the number of perfect matchings in G. The FKT algorithm does such a task for a planar graph G.

Let G = (V, E) be an undirected graph with adjacency matrix 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{PerfMatch}(G) = \sum_{M \in PM(|V|)} \prod_{(i,j) \in M} A_{i j}.

Closely related to this is the Pfaffian for an n by n matrix A

\operatorname{pf}(A) = \sum_{M \in PM(n)} \operatorname{sgn}(M) \prod_{(i,j) \in M} A_{i j},

where sgn(M) is the sign of the permutation M. A Pfaffian orientation of G is a directed graph H with (1, −1, 0)-adjacency matrix B such that pf(B) = PerfMatch(G).[9] 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 A,

\operatorname{pf}(A)^2 = \det(A),

where det(A) is the determinant of A. This result is due to Cayley.[10] Since determinants are efficiently computable, so is PerfMatch(G).

High-level description

An example showing how the FKT algorithm finds a Pfaffian orientation.
  1. Compute a planar embedding of G.
  2. Compute a spanning tree T1 of the input graph G.
  3. Give an arbitrary orientation to each edge in G that is also in T1.
  4. Use the planar embedding to create an (undirected) graph T2 with the same vertex set as the dual graph of G.
  5. Create an edge in T2 between two vertices if their corresponding faces in G share an edge in G that is not in T1. (Note that T2 is a tree.)
  6. For each leaf v in T2 (that is not also the root):
    1. Let e be the lone edge of G in the face corresponding to v that does not yet have an orientation.
    2. Give e an orientation such that the number of edges oriented clock-wise is odd.
    3. Remove v from T2.
  7. Return the absolute value of the Pfaffian of the (1, −1, 0)-adjacency matrix of G, which is the absolute value of the square root of the determinant.

Generalizations

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

Kuratowski's theorem states that

a finite graph is planar if and only if it contains no subgraph homeomorphic to K5 (complete graph on five vertices) or K3,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 to K3,3.[11] 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, is also #P-complete even for planar graphs.[12]

Applications

The FKT algorithm has seen extensive use in holographic algorithms on planar graphs via matchgates.[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.[13]

References

  1. ↑ Hayes, Brian (January–February 2008), "Accidental Algorithms", American Scientist
  2. ↑ Baxter, R. J. (2008) [1982]. Exactly Solved Models in Statistical Mechanics (Third ed.). Dover Publications. p. 11. ISBN 978-0-486-46271-4.
  3. ↑ 3.0 3.1 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2010). Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. Las Vegas, NV, USA: IEEE. arXiv:1008.0683.
  4. ↑ Kenyon, Richard; Okounkov, Andrei (2005). "What is a Dimer?". AMS 52 (3): 342–343.
  5. ↑ Kasteleyn, P. W. (1961), "The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice", Physica 27 (12): 1209–1225, doi:10.1016/0031-8914(61)90063-5
  6. ↑ Temperley, H. N. V.; Fisher, Michael E. (1961). "Dimer problem in statistical mechanics-an exact result". Philosophical Magazine 6 (68): 1061–1063. doi:10.1080/14786436108243366.
  7. ↑ Kasteleyn, P. W. (1963). "Dimer Statistics and Phase Transitions". Journal of Mathematical Physics 4 (2): 287–293. doi:10.1063/1.1703953.
  8. ↑ Kasteleyn, P. W. (1967), "Graph theory and crystal physics", in Harary, F., Graph Theory and Theoretical Physics, New York: Academic Press, pp. 43–110
  9. ↑ Thomas, Robin (2006). A survey of Pfaffian orientations of graphs. International Congress of Mathematicians III. Zurich: European Mathematical Society. pp. 963–984.
  10. ↑ Cayley, Arthur (1847). "Sur les determinants gauches" [On skew determinants]. Crelle's Journal 38: 93–96.
  11. ↑ Vazirani, Vijay V. (1989). "NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems". Information and Computation 80 (2): 152–164. doi:10.1016/0890-5401(89)90017-5. ISSN 0890-5401.
  12. ↑ Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable", Journal of Statistical Physics 48 (1): 121–134, doi:10.1007/BF01010403.
  13. ↑ Valiant, Leslie G. (2004). "Holographic Algorithms (Extended Abstract)". Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. FOCS'04. Rome, Italy: IEEE Computer Society. pp. 306–315. doi:10.1109/FOCS.2004.34. ISBN 0-7695-2228-9.

External links