FKT algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in an undirected planar graph in polynomial time. 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 solved efficiently using standard determinant algorithms.
History
In statistical mechanics, the partition function is an important quantity that encodes the statistical properties of a system at equilibrium. 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.[1] In the early 1960's, the definitions of practical and sufficiently simple were not rigorous.[2] Computer science provided rigorous definitions with the introduction of polynomial time, which dates to 1965.
One 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.[3] 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[4] and Temperley-Fisher[5] 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.[6][7]
The Algorithm
Here is the algorithm at a high level:
- Compute a spanning tree T1 of the input graph G
- Give an arbitrary orientation to each edge in T1
- Compute a planar embedding of G
- Use the planar embedding to create an (undirected) graph T2 with the same vertex set as the dual graph of G
- Create an edge in T2 between two vertices if their corresponding faces in G share an edge in G that is not in T1
- For each leaf v in T2 (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 T2
- Return the absolute value of the Pfaffian of the Tutte matrix of G
Generalizations
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 six vertices, three of which connect to each of the other three).
Vijay Vazirani generalized the FKT algorithm to graphs which do not contain a subgraph homeomorphic to K3,3.[8]
Applications
The FKT algorithm has seen extensive use in holographic algorithms on planar graphs via matchgates. For example, consider the planar version of the ice model mentioned above, which has the tecnical name #PL-3-NAE-SAT (where NAE stands for "not all equal"). Valiant found a polynomial time algorithm for this problem which uses matchgates.[9]
References
- ^ Baxter, R. J. (2008) [1982]. Exactly Solved Models in Statistical Mechanics (Third ed.). Dover Publications. p. 11. ISBN 978-0486462714.
{{cite book}}: More than one of|pages=and|page=specified (help) - ^ 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.
{{cite conference}}: External link in|conferenceurl=|conferenceurl=ignored (|conference-url=suggested) (help) - ^ Kenyon, Richard; Okounkov, Andrei (2005). "What is a Dimer?" (PDF). AMS. 52 (3): 342–343.
- ^ 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
- ^ 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.
- ^ Kasteleyn, P. W. (1963). "Dimer Statistics and Phase Transitions". Journal of Mathematical Physics. 4 (2): 287–293. doi:10.1063/1.1703953.
- ^ Kasteleyn, P. W. (1967), "Graph theory and crystal physics", in Harary, F. (ed.), Graph Theory and Theoretical Physics, New York: Academic Press, pp. 43–110
- ^ Vazirani, Vijay V. (1988), "NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems", Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT '88), Lecture Notes in Computer Science, vol. 318, Springer-Verlag, pp. 233–242, doi:10.1007/3-540-19487-8_27.
- ^ 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.
{{cite conference}}: External link in|conferenceurl=|booktitle=ignored (|book-title=suggested) (help); Unknown parameter|conferenceurl=ignored (|conference-url=suggested) (help)
External Links
- Presentation by Ashley Montanaro about the FKT algorithm