arXiv preprint ·
Hidden Circuits and Exact Counting in Ordered Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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).
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Almost Optimal FPT Inapproximability for k-SetCover
Human Language Shapes the Emerging Physical Reasoning in Large Language Models
Learning Depth-3 Circuits with Polynomial Savings
Weighted Quantum Signal Processing: Low-Depth Polynomial Approximation with Applications to Kolmogorov-Arnold Networks
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.