Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems

Kazuki Matoya, Taihei Oki

TL;DR

This paper introduces "Pfaffian parities" as a generalization of "Pfaffian pairs" to linear matroid parity problems. The authors unify various combinatorial structures under this framework, deriving celebrated counting theorems and presenting efficient algorithms for both unweighted and weighted versions of these problems, including derandomization of existing algorithms.

What Problem Does This Paper Address?

The paper tackles the challenge of efficiently counting combinatorial objects that arise in various areas of mathematics and computer science, such as spanning trees and perfect matchings. While some of these objects, like bases of regular matroids and perfect matchings of Pfaffian graphs, are known to be efficiently countable, generalizing these results to broader classes of problems like linear matroid intersection and parity problems has been an ongoing effort. The authors aim to provide a unified framework that not only explains existing results but also extends them to new problems and offers improved algorithmic solutions. Specifically, they address the problem of counting common bases of linear matroids and parity bases of linear matroid parities, and their weighted variants.

Methods

The core of the paper's contribution lies in introducing and formalizing the concept of "Pfaffian parities" as an extension of "Pfaffian pairs." This new concept allows for the tractable counting of parity bases in linear matroid parity problems. The authors leverage generalizations of the Cauchy-Binet formula and the Pfaffian definition to establish theoretical results. They then demonstrate how this unified framework can derive known counting theorems like Kirchhoff's matrix-tree theorem and the Lindström-Gessel-Viennot lemma.

Algorithmically, the paper focuses on two main aspects:

  1. Derandomization: They show that existing randomized algorithms for linear matroid intersection and parity problems can be derandomized for Pfaffian pairs and parities, achieving deterministic polynomial-time complexity. This is achieved by exploiting the specific properties of Pfaffian structures that avoid numerical cancellations.
  2. Weighted Counting: For weighted versions of these problems, they develop polynomial-time algorithms to count minimum-weight solutions. This involves techniques like Frank's weight splitting lemma and algebraic optimality criteria, reducing the weighted problem to unweighted counting or leveraging specialized algorithms for graph problems.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unification through Pfaffian Parities: The introduction of "Pfaffian parities" provides a powerful unifying concept that connects seemingly disparate combinatorial problems under a single theoretical umbrella. This allows for a more systematic study and development of counting algorithms.
  • Algorithmic Efficiency: The paper demonstrates that the specific structure of Pfaffian pairs and parities allows for significant algorithmic improvements, including the derandomization of previously randomized algorithms and efficient counting for weighted problems.
  • Connections to Existing Theorems: The ability to derive well-known theorems like the matrix-tree theorem and the LGV lemma from this new framework highlights its foundational importance and broad applicability.
  • Bridging Theory and Practice: The paper successfully bridges theoretical advancements in combinatorial theory with practical algorithmic solutions, offering both deeper understanding and efficient computational tools.

Key Results

  • Formal definition of "Pfaffian parities" and demonstration of their utility in unifying various combinatorial structures.
  • Derandomization of state-of-the-art randomized algorithms for linear matroid intersection and parity problems for Pfaffian structures, achieving deterministic polynomial-time complexity.
  • Development of polynomial-time algorithms for counting minimum-weight common bases of Pfaffian pairs and minimum-weight parity bases of Pfaffian parities.
  • Derivation of celebrated counting theorems (e.g., matrix-tree theorem, LGV lemma) as corollaries within the Pfaffian pair/parity framework.

Limitations and Future Work

  • Characteristic of Field: While the algorithms are presented for fields K, the derandomization results are specifically proven for fields with characteristic 0. Extending these to arbitrary characteristics might be a future direction.
  • Practical Performance: While polynomial-time algorithms are presented, their practical performance on large instances, especially for the weighted problems, might depend on the efficiency of underlying subroutines and the specific constants involved.
  • Further Applications: The paper suggests that the Pfaffian pair/parity framework could be applied to other combinatorial problems, and exploring these connections remains an avenue for future research. The authors also pose a conjecture regarding the relationship between weighted Pfaffian parities and graph structures that could be further investigated.

Summary updated

Abstract

Spanning trees are a representative example of linear matroid bases that are efficiently countable. Perfect matchings of Pfaffian bipartite graphs are a countable example of common bases of two matrices. Generalizing these two examples, Webb (2004) introduced the notion of Pfaffian pairs as a pair of matrices for which counting of their common bases is tractable via the Cauchy-Binet formula. This paper studies counting on linear matroid problems extending Webb's work. We first introduce "Pfaffian parities" as an extension of Pfaffian pairs to the linear matroid parity problem, which is a common generalization of the linear matroid intersection problem and the matching problem. We enumerate combinatorial examples of Pfaffian pairs and parities. The variety of the examples illustrates that Pfaffian pairs and parities serve as a unified framework of efficiently countable discrete structures. Based on this framework, we derive celebrated counting theorems, such as Kirchhoff's matrix-tree theorem, Tutte's directed matrix-tree theorem, the Pfaffian matrix-tree theorem, and the Lindström-Gessel-Viennot lemma. Our study then turns to algorithmic aspects. We observe that the fastest randomized algorithms for the linear matroid intersection and parity problems by Harvey (2009) and Cheung-Lau-Leung (2014) can be derandomized for Pfaffian pairs and parities. We further present polynomial-time algorithms to count the number of minimum-weight solutions on weighted Pfaffian pairs and parities. Our algorithms make use of Frank's weight splitting lemma for the weighted matroid intersection problem and the algebraic optimality criterion of the weighted linear matroid parity problem given by Iwata-Kobayashi (2017).
BibTeX
@inproceedings{matoya2021pfaffian,
  author = {Kazuki Matoya and Taihei Oki},
  title = {{Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems}},
  booktitle = {IPCO},
  year = {2021},
  doi = {10.1007/978-3-030-73879-2\_16},
}
Figure