Подсчет числа совершенных паросочетаний и обобщенные разрешающие деревья

Изучается обобщение подхода Пойа – Кастелейна к подсчету числа совершенных паросочетаний в графах, основанное на вычислении символического пфаффиана ориентированной матрицы смежности графа. Трудоемкость алгоритмов, основанных на таком подходе, связана со сложностью функции знака совершенного паросочетания в моделях обобщенных разрешающих деревьев. Получены нижние оценки сложности знака совершенного паросочетания через детерминированную коммуникационную сложность XOR-функции знака паросочетания. Эти оценки показывают ограничения метода символического пфаффиана как для общего случая, так и для случая разреженных графов.