Counting spanning quasi-trees of ribbon graphs: determinants and #P-completeness

Abstract

A quasi-tree of a connected ribbon graph is a spanning ribbon subgraph with exactly one boundary component; quasi-trees play the role of spanning trees in the topological graph theory of embedded graphs. We prove that counting them is #P-complete under polynomial-time Turing reductions, already for bouquets. The proof identifies every nonempty framed chord diagram, up to natural identifications, with a 4-regular map equipped with a distinguished A-trail, in such a way that quasi-trees correspond to A-trails, whose counting is #P-complete by a theorem of Ge and Štefankovič. Through the framed Cohn-Lempel equality the count is also an interlace-polynomial evaluation - $q(H;2,1)$, the number of full-rank induced subgraphs of the looped circle graph $H$ of the diagram - placing it on the line $y=1$ left open in the complexity classification of Bläser and Hoffmann; a cloning argument then makes every fixed rational point of that line, other than the trivial $(1,1)$, #P-hard on looped circle graphs, even when a framed chord representation is supplied. On the tractable side, the same GF(2) model yields short proofs of the known determinantal cases: for orientable ribbon graphs the count is a determinant, essentially the Matrix-Quasi-tree Theorem of Merino, Moffatt and Noble, proved here via Bouchet's principal unimodularity, and for bouquets with exactly one non-orientable loop it is a sum of two orientable determinants, equivalent by a rank-one determinant identity to the determinant formula of Deng, Jin and Yan.

Disclosure

“lass — diagrams with several loops may still lie in larger determinantal classes [22], Conjecture 6.2 proposing a characterization of the detectable class — with every rational point (ξ, 1), ξ ̸= 1, #P-hard alongside it. Acknowledgements Claude Fable 5 and GPT-5.6 Sol Pro were used extensively in the development and prepa- ration of this work. References [1] Lars Døvling Andersen, André Bouchet, and Bill Jackson. Orthogonal A-trails of 4-regular graphs embedded in surface”

PDF page 23

Classification

Brainstorming or outlining

Multiplier

2

Verified

2026-08-23T19:00:54.648737Z

Structural counts