Counting perfect matchings is hard in several ordered graph classes
Hidden Circuits and Exact Counting in Ordered Graphs
Computational ComplexityData Structures and Algorithms
Summary
Counting perfect matchings in graphs is a classic hard problem in computer science. This paper shows that even for certain simple-looking ordered graphs, called monotone, unit interval, and chordal permutation graphs, counting perfect matchings exactly remains very hard. The authors use ideas inspired by quantum circuits to simulate computations within graphs, making this hardness rigorous. They also improve algorithms for related graph classes, completing a classification of exact counting difficulty for many structured graphs.
What this means in practice
- •For graph algorithm designers: Avoid seeking efficient exact counting algorithms for perfect matchings in monotone, unit interval, and chordal permutation graphs, since this paper proves it is computationally infeasible.
- •For complexity theorists: Use the quantum-inspired reduction techniques to study hardness of related counting problems, extending tools for showing deep complexity results in graph classes.
A theory result. No direct application yet.
Authors
Chenghua Liu, Boning Meng
Abstract
We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and Müller (JACM 2017), complementing their rapid-mixing theorem. Inspired by quantum circuits, our reductions implement a circuit simulation using globally coupled matching-transfer operators. The key construction is an exact projection, implemented by a polynomial-length sequence of normalized transfers, that restores tensor-product locality and makes encoded gates composable. Interpolation-based cancellation then reduces circuit evaluation to unweighted perfect-matching counts in all three classes. We also place Dyer and Müller's class QChains within the distance-hereditary graphs and give an $O(n^2)$-arithmetic-operation counting algorithm for the latter, improving the $O(n^4)$ bound obtainable from Curticapean and Marx (SODA 2016). Together with prior results, these advances complete the exact-counting classification of the graph classes in Dyer and Müller's diagram (SIDMA 2019).