Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
Abstract
We introduce a new elementary technique for proving #P-hardness results under Turing reductions, and showcase its applicability by settling the counting complexity of several fundamental problems about counting orderings in graphs, posets, and geometric configurations. The technique addresses a natural difficulty in counting reductions: when designing gadgets that attempt to enforce a semantic property, the introduction of the gadgets themselves can affect the function to count in complicated ways. In a nutshell, we introduce an amplification parameter q for the gadgets (e.g., replacing a subset of the vertices of a graph by q copies) and show that the limiting behavior when q tends to infinity, or even to negative values, filters out the unwanted effects of the gadgets, which allows us to recover the desired counts. These limits can be computed symbolically via interpolation, after showing that the probability of a random ordering satisfying the problem's constraints is a rational function in q. Concretely, with this methodology, we show #P-completeness for counting the following objects: (a) successive vertex orderings, even on bipartite graphs, (b) st-numberings of graphs, (c) shellings, even for bipartite graphs, (d) perfect elimination orderings, even for split graphs, (e) linear extensions of N-free posets of height $3$, (f) linear extensions of posets of height $2$, and (g) peeling sequences of point sets. Result (e) settles a conjecture of Felsner and Manneville (2015), and although result (f) was first proved by Dittmer and Pak (2018), we include an alternative proof, using our technique, that does not rely on the result of Brightwell and Winkler (1991) about hardness of counting for general posets. Result (g) answers a question of Eppstein.
Related
BibTeX
@misc{arenas2026hardness,
title = {{Hardness of Counting Orderings: Taking Gadget Amplification to the Limit}},
author = {Marcelo Arenas and María Alejandra Schild and Bernardo Subercaseaux},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2606.29157},
eprint = {2606.29157},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.29157},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
AU - Marcelo Arenas
AU - María Alejandra Schild
AU - Bernardo Subercaseaux
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2606.29157
UR - https://arxiv.org/abs/2606.29157
AB - We introduce a new elementary technique for proving #P-hardness results under Turing reductions, and showcase its applicability by settling the counting complexity of several fundamental problems about counting orderings in graphs, posets, and geometric configurations. The technique addresses a natural difficulty in counting reductions: when designing gadgets that attempt to enforce a semantic property, the introduction of the gadgets themselves can affect the function to count in complicated ways. In a nutshell, we introduce an amplification parameter q for the gadgets (e.g., replacing a subset of the vertices of a graph by q copies) and show that the limiting behavior when q tends to infinity, or even to negative values, filters out the unwanted effects of the gadgets, which allows us to recover the desired counts. These limits can be computed symbolically via interpolation, after showing that the probability of a random ordering satisfying the problem's constraints is a rational function in q. Concretely, with this methodology, we show #P-completeness for counting the following objects: (a) successive vertex orderings, even on bipartite graphs, (b) st-numberings of graphs, (c) shellings, even for bipartite graphs, (d) perfect elimination orderings, even for split graphs, (e) linear extensions of N-free posets of height $3$, (f) linear extensions of posets of height $2$, and (g) peeling sequences of point sets. Result (e) settles a conjecture of Felsner and Manneville (2015), and although result (f) was first proved by Dittmer and Pak (2018), we include an alternative proof, using our technique, that does not rely on the result of Brightwell and Winkler (1991) about hardness of counting for general posets. Result (g) answers a question of Eppstein.
ER -