algorithme FKT

L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et Harold N. Temperley, compte le nombre de couplages parfaits dans un graphe planaire, et ceci en temps polynomial. Le même dénombrement est #P-complet pour les graphes généraux. Pour les couplages qui ne sont pas nécessairement parfaits, leur dénombrement reste #P-complet même pour les graphes planaires. L'idée clé de l'algorithme FKT est de convertir le problème en le calcul du pfaffien d'une matrice antisymétrique obtenue à partir d'un plongement planaire du graphe. Le pfaffien de cette matrice est ensuite calculé efficacement à l'aide d'algorithmes standards pour les déterminants .