{"id":"arxiv/2606.29157","url":"https://arxiv.org/abs/2606.29157","tags":["cs.CC","math.CO"],"score":0,"title":"On the Complexity of Counting Orderings in Graphs","domain":"cs.CC","source":"arxiv","authors":["Marcelo Arenas","María Alejandra Schild","Bernardo Subercaseaux"],"reviews":0,"subject":"cs.CC","summary":"We study the computational complexity of several counting problems on graphs. Each of these problems consists of counting orderings of the vertices or edges with adjacency constraints. We show $\\#P$-completeness for all of them via a common new technique. Given a counting function $C$ of interest, we define a parameterized family of instances $G_q$, where the parameter $q$ controls the amplification of a simple gadget. After multiplying by an explicit factor $f(q)$, we show that the values of $f(q) \\cdot C(G_q)$, for positive integers $q$, agree with a rational function in $q$ whose…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-28","reactions":{}}