Алгоритм FKT

FKT (назван по именам Фишера, и ) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.