FKT algorithm

<p>
The Fisher–Kasteleyn–Temperley (FKT) algorithm, named after <a href="/facts/Michael_Fisher/doa77cqa">Michael Fisher</a>, <a href="/facts/Pieter_Kasteleyn/qBUkvwR8">Pieter Kasteleyn</a>, and <a href="/facts/Harold_Neville_Vazeille_Temperley/FvuabWP0">Neville Temperley</a>, counts the number of <a href="/facts/Perfect_matching/LmtRYLgK">perfect matchings</a> in a <a href="/facts/Planar_graph/plREagr9">planar</a> graph in polynomial time. This same task is <a href="/facts/Sharp-P-complete/M6QgPJY6">#P-complete</a> for general graphs. For <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matchings</a> 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 <a href="/facts/Pfaffian/3CmddqLu">Pfaffian</a> computation of a <a href="/facts/Skew-symmetric_matrix/nw5CQeLN">skew-symmetric matrix</a> derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard <a href="/facts/Determinant/eGYqJ2TF">determinant algorithms</a>.
</p>

FKT algorithm open-in-new

FKT algorithm