Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Hardness of Counting Orderings".
Jane: Here's the gist of the paper. On the complexity of counting orderings in graphs, this paper establishes that several counting problems involving vertex or edge orderings with adjacency constraints are all hard to compute in polynomial time via a common new technique via a common new technique.
Tom: Hardness Results for Orderings The authors show that they establish the hardness of counting successive vertex orderings (SVOs) of bipartite graphs, st-numberings of graphs, shellings of bipartite graphs, linear extensions of N-free posets of height 3, and linear extensions of posets of height 2 via a common new technique.
Jane: They prove that membership in the class is immediate because verification is possible in polynomial time.
Tom: Specifically, they show that for counting linear extensions of N-free posets of height 3, they settle a conjecture by proving its hardness.
Paper summary: Tom: So we've talked about what the paper is proving—that several counting problems involving vertex or edge orderings with adjacency constraints are hard to compute in polynomial time via a common new technique.
Jane: To summarize, the authors define this parameterized family of instances Gq where q controls the amplification of a simple gadget, and after multiplying by an explicit factor f of q, they show that these values agree with a rational function in q.
Lu: They then recover this hard to count function by evaluating that rational function symbolically at a limiting value L, which can be some value in Q or infinity or negative infinity.
Meng: This entire methodology is what they use to prove hardness for successive vertex orderings of bipartite graphs, st-numberings of graphs, shellings of bipartite graphs, and linear extensions of N-free posets with height three.
Lalam: They also apply this technique to linear extensions of posets with height two. And they specifically settled a conjecture about counting linear extensions of N-free posets with height three by proving its hardness.
Tom: It's interesting how they prove membership in the class is immediate because verification is possible in polynomial time, which makes it a very strong result about how hard these problems are.
Jane: They also showed that for shellings, they can strengthen the hardness result to include split graphs by modifying the construction used for rooted SVOs.
Lu: And they noted that all of these reductions could be adapted so that they start from an instance of the exact two-cover problem instead of just the three-cover problem <ref:2606.29157#pg1>.
Meng: So, this paper establishes hardness for a wide range of graph structures and posets using a single, unified technique centered around gadget amplification.
Lalam: It’s quite comprehensive in its scope, covering things from simple bipartite graphs to more complex N-free posets with height three.
Conclusion: Tom: So we've gone through the paper "Hardness of Counting Orderings: Taking Gadget Amplification to the Limit" and seen that it establishes #P-completeness for counting successive vertex orderings, st-numberings, shellings, and linear extensions of posets.
Jane: The authors used a common new technique involving gadget amplification to show that these problems are hard because they can't find a fast way to count them.
Lu: What this means for the world is that it sets a high bar for us when we think about finding efficient algorithms for counting structures in graphs or posets.
Meng: It tells us that unless there’s some unexpected structural property we haven't seen, we should probably assume these counting problems are inherently hard to solve quickly.
Lalam: The paper settles the conjecture about linear extensions of N-free posets with height three by proving its hardness, which is a big deal for that specific class of posets.
Tom: Overall, the title "Hardness of Counting Orderings: Taking Gadget Amplification to the Limit" perfectly captures what they did—they took an amplification technique and pushed it to its limit to show these counting problems are intractable in polynomial time.
Universidad Catolica de Chile · Carnegie Mellon University
cs.CC, math.CO
Submitted: 2026-06-28
Updated: 2026-11-04
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 97/100
The gist: On the complexity of counting orderings in graphs, this paper establishes that several counting problems involving vertex or edge orderings with adjacency constraints are all hard to compute in…
Key concepts
- Successive Vertex Orderings (SVOs)
- This involves finding an ordering of the vertices in a bipartite graph such that each vertex is adjacent only to vertices appearing earlier in the ordering. Counting these specific orderings is shown to be hard.
- Gadget Amplification
- This is a core technique where a simple structure (gadget) is repeatedly multiplied by an explicit factor. This amplification allows the authors to create instances where counting becomes equivalent to evaluating a rational function at a specific limit.
- Rational Function Interpolation
- The method uses the results from many integer inputs ($q$) to determine a rational function that describes the count. This function is then used symbolically to find the exact count by evaluating it at a specific limiting value, which is computationally feasible.
Terminology
Summary
On the complexity of counting orderings in graphs, this paper establishes that several counting problems involving vertex or edge orderings with adjacency constraints are all hard to compute in polynomial time via a common new technique via a common new technique. p. 0 Each
of them 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.Where the paper says it
Hardness Results for Orderings
The authors show that they establish the hardness of counting successive vertex orderings (SVOs) of bipartite graphs, st-numberings of graphs, shellings of bipartite graphs, linear extensions of N-free posets of height 3, and linear extensions of posets of height 2 via a common new technique. They prove that membership in the class is immediate because verification is possible in polynomial time. p. 0 We prove #P-hardness under Turing
reductions in all four settings. Since in all these problems it is possible to verify in polynomial time
whether some permutation is valid, membership in the class #P is immediate, so we indeed obtain
#P-completeness for all of them. 1b shows the Hasse diagram
of a poset, where vertex c acts as an and: both a and b must be placed before c is available. Second, we resolve a conjecture of Felsner and Manneville [FM15] by proving #P-hardness for
counting linear extensions of N-free posets of height 3 (a poset is said to be N-free if its Hasse
diagram does not contain the ‘N’ pattern displayed in Figure 1.Where the paper says it
Where the paper says it
The Core Methodology
The main idea involves defining a parameterized family of instances Gq where the parameter q controls the amplification of a simple gadget. After multiplying by an explicit factor f(q), they show that the values of f(q) · C(Gq), for positive integers q, agree with a rational function in q whose numerator and denominator can be interpolated in polynomial time. p. 0 Given a counting function C
of interest, we define a parameterized family of instances Gq, 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) · C(Gq), for positive integers q, agree with a rational function in q whose numerator
and denominator can be interpolated in polynomial time. After multiplying by an explicit factor f(q), we show that the
values of f(q) · C(Gq), for positive integers q, agree with a rational function in q whose numerator
and denominator can be interpolated in polynomial time. We then recover a #P-hard function by
evaluating this rational function symbolically at a limiting value L ∈ Q ∪ {∞, −∞}.Where the paper says it
Where the paper says it
Reductions and Gadgets
The hardness proofs for counting SVOs and Shellings share the same structure, reducing from the counting version of the exact 3-cover problem (X3C). For SVOs, they construct a bipartite graph GI,q where each element of U is replaced by q distinct copies that are indistinguishable in terms of adjacencies. p. 2 The parameter q controls the number of copies of simple gadgets. For example, in the reduction
to #SVO, each element of U is replaced by q distinct copies that are indistinguishable in terms
of adjacencies. 1b shows the Hasse diagram
of a poset, where vertex c acts as an and: both a and b must be placed before c is available. Second, we resolve a conjecture of Felsner and Manneville [FM15] by proving #P-hardness for
counting linear extensions of N-free posets of height 3 (a poset is said to be N-free if its Hasse
diagram does not contain the ‘N’ pattern displayed in Figure 1.Where the paper says it
Where the paper says it
Recovering the Hard Function
The authors demonstrate that they can compute two polynomials R and D in canonical form such that the equality between rational functions holds: Xσ∈[n]! χσ(q) = R(q) / D(q). p. 5 =
X
σ∈[n]! χσ(q),
where
χσ(q) :=
1
Qn
i=1
i +
Pi
j=1 q · cn−j+1(σ)
. What we do instead is show that the normalized counting function agrees, for all
positive integers q, with a rational function in q whose denominator is explicitly known and has
polynomial degree. Thus, using an oracle for the target counting problem, we can interpolate the
numerator of the rational function exactly by evaluating the normalized count for polynomially
many positive integer values of q. Since q
hR(q)
D(q)
is a ratio of polynomials, of size polynomial in the size of I, the limit can be computed
symbolically in polynomial time, as it corresponds simply to the ratio of the leading coefficients. □
We will now show how to obtain Theorem 1.Where the paper says it
Where the paper says it
Where the paper says it
Shellings and Linear Extensions
For shellings, they prove Theorem 1.2 by showing that counting rooted shellings of a bipartite graph G with root r is hard. p. 0 We then recover a #P-hard function by
evaluating this rational function symbolically at a limiting value L ∈ Q ∪ {∞, −∞}. With this
methodology, we show #P-completeness for the following counting problems: (a) successive vertex
orderings of bipartite graphs, (b) st-numberings of graphs, (c) shellings of bipartite graphs, (d)
linear extensions of N-free posets of height 3, and (e) linear extensions of posets of height 2. In X3C, we are given a collection of
sets S := {S1, . , Sn}, each of which consists of 3 elements from a universe U := {u1, . We then recover a #P-hard function by
evaluating this rational function symbolically at a limiting value L ∈ Q ∪ {∞, −∞}. With this
methodology, we show #P-completeness for the following counting problems: (a) successive vertex
orderings of bipartite graphs, (b) st-numberings of graphs, (c) shellings of bipartite graphs, (d)
linear extensions of N-free posets of height 3, and (e) linear extensions of posets of height 2. We then recover a #P-hard function by
evaluating this rational function symbolically at a limiting value L ∈ Q ∪ {∞, −∞}. With this
methodology, we show #P-completeness for the following counting problems: (a) successive vertex
orderings of bipartite graphs, (b) st-numberings of graphs, (c) shellings of bipartite graphs, (d)
linear extensions of N-free posets of height 3, and (e) linear extensions of posets of height 2.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Concluding the Proof
The final steps involve using the interpolation framework to recover the exact count from the rational function, and then multiplying this limit by a factor to obtain the desired counting problem, such as multiplying by 3h for SVOs. The proof concludes that counting linear extensions of height-2 posets is also hard. p. 0 We then recover a #P-hard function by
evaluating this rational function symbolically at a limiting value L ∈ Q ∪ {∞, −∞}. With this
methodology, we show #P-completeness for the following counting problems: (a) successive vertex
orderings of bipartite graphs, (b) st-numberings of graphs, (c) shellings of bipartite graphs, (d)
linear extensions of N-free posets of height 3, and (e) linear extensions of posets of height 2.Where the paper says it
The authors show that the hardness result for shellings can be strengthened to include split graphs by modifying the construction for rooted SVOs. They also note that all reductions could be adapted so that they start from an instance of the exact 2-cover problem (X2C). p. 2 the set of all permutations of X. To prove our results, we will reduce from the counting version of the exact 3-cover problem (X3C)
for which NP-hardness of the decision version is well known.Where the paper says it
Consequences for Planar Graphs
The authors suggest a natural open direction, noting that the complexity of the planar variants of these counting problems remains open to their knowledge. The first obstruction is the presence of a root vertex adjacent to all set vertices, which appears in several constructions and can be incompatible with some planar embedding of the incidence graph. p. 0 Given an undirected graph G = (V, E) on n vertices, a
successive vertex ordering (SVO) of G is an ordering (v1, . , vn) of its vertices such that for each
2 ⩽ i ⩽ n, vertex vi
is adjacent to some vj with j < i. 1b shows the Hasse diagram
of a poset, where vertex c acts as an and: both a and b must be placed before c is available. Second, we resolve a conjecture of Felsner and Manneville [FM15] by proving #P-hardness for
counting linear extensions of N-free posets of height 3 (a poset is said to be N-free if its Hasse
diagram does not contain the ‘N’ pattern displayed in Figure 1.Where the paper says it
Where the paper says it
Acknowledgments
Part of this work has been funded by ANID - Millennium Science Initiative Program - Code ICN17002. The second author was also financially supported by ANID (Doctorado Nacional, 2025, folio 21251617). p. 1 Once again, the number of shellings has been studied for specific classes such as trees
and complete bipartite graphs [GP21]. Further results on shellings of graphs were presented in the
master’s thesis of the second author [Sch24]. There is also a natural duality between shellings of undirected graphs and linear extensions of
edge posets, as the former imposes a disjunctive condition over edge orderings, while the latter
imposes a conjunctive condition. As we will see, the proofs of Theorem 1. In 2018, Goaoc, Pat´ak, Pat´akov´a, Tancer, and Wagner settled a long-standing open question by
showing that deciding whether a d-dimensional simplicial complex is “shellable” is NP-complete
for d ⩾ 2 [GPP+19]. Since 1-dimensional simplicial complexes are just graphs, Theorem 1. All our hardness proofs follow a common interpolation scheme,
which is described in Section 2. The main idea is to use oracle evaluations on amplified instances to
determine a rational function, from which a hard-to-count quantity can be recovered as a limiting
value that can be computed symbolically.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Computational complexity analysis for graph counting problems: The system can determine if counting successive vertex orderings (SVO), st-numberings, shellings of bipartite graphs, linear extensions of N-free posets of height 3, or linear extensions of posets of height 2 are computationally intractable by reducing them to the exact 3-cover problem.
-
Polynomial time computation via oracle queries: The system can compute counting functions like SVO(G; r) or Shellings(G; r) in polynomial time for bipartite graphs by using repeated calls to an oracle for the unrooted variant and applying Lagrange interpolation, as shown in Proposition 3.5 and 5.4.
-
Recovering hard counts from rational functions: The system can recover a hard-to-count quantity, such as the number of exact covers in an instance of the exact 2-cover problem, by evaluating a rational function derived from oracle evaluations at specific points and applying symbolic limit computation (Proposition 3.4).
-
Verification of structural properties through counting: The system can verify that a permutation induces an exact cover or not by analyzing the coefficients Ci,sigma based on its position in the ordering, as described in Claim 6.1 and Claim 5.2.
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.
Sources
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
- Interactive Proofs of Proximity for Model Evaluation