Counting perfect matchings in graphs that exclude a single-crossing minor

Abstract

A graph $H$ is single-crossing if it can be drawn in the plane with at most one crossing. For any single-crossing graph $H$, we give an $O(n^4)$ time algorithm for counting perfect matchings in graphs excluding $H$ as a minor. The runtime can be lowered to $O(n^{1.5})$ when $G$ excludes $K_5$ or $K_{3,3}$ as a minor. This is the first generalization of an algorithm for counting perfect matchings in $K_{3,3}$-free graphs (Little 1974, Vazirani 1989). Our algorithm uses black-boxes for counting perfect matchings in planar graphs and for computing certain graph decompositions. Together with an independent recent result (Straub et al. 2014) for graphs excluding $K_5$, it is one of the first nontrivial algorithms to not inherently rely on Pfaffian orientations.

7 pages, 2 figures

Cited by in corpus (2)

• A New Family of Tractable Ising Models
• Parameterizing the Permanent: Hardness for $K_8$-minor-free graphs