The FKT algorithm is used to count the number of perfect matchings in a planar graph in polynomial time. It is #P-complete for general graphs, and even for planar graphs when matchings are not required to be perfect. The algorithm works by converting the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph.
Stanford University
Autumn 2022
The course addresses both classic and recent developments in counting and sampling. It covers counting complexity, exact counting via determinants, sampling via Markov chains, and high-dimensional expanders.
No concepts data
+ 52 more concepts