The celebrated matrix-tree theorem, which is to count the number of spanning trees in graphs, is a theorem essentially for counting bases of general regular matroids. Webb (2004) introduced the notion of Pfaffian pairs as a pair of regular matroids for which counting of their common bases is tractable through the matrix-tree theorem. This class can represent a bunch of important combinatorial structures, such as spanning trees, arborescences, Euler tours in 4-regular digraphs and perfect matchings in K_{3,3}-free bipartite graphs. In this talk, as an application of the matrix-tree theorem for Pfaffian pairs, we present deterministic polynomial-time algorithms for several counting problems: exact, group-labeled and weighted problem settings.

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria www.ist.ac.at © IST 2021