Hardness of Counting Orderings: Taking Gadget Amplification to the Limit

arXiv:2606.29157 · cs.CC, math.CO · Submitted 2026-06-28 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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.

Specifically, they show that for counting linear extensions of N-free posets of height 3, they settle a conjecture by proving its hardness. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

They then recover a hard-to-count function by evaluating this rational function symbolically at a limiting value L ∈ Q ∪ Q U ∞, −∞. p. 0
Where the paper says it

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 ∪ {∞, −∞}.

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

Where the paper says it

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.

Similarly, for linear extensions of height-2 posets, they construct a poset PI,q where relations are defined based on the sets Si. p. 1
Where the paper says it

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.

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

Where the paper says it

= X σ∈[n]! χσ(q), where χσ(q) := 1 Qn i=1 i + Pi j=1 q · cn−j+1(σ) .

They obtain these polynomials by evaluating the normalized count for polynomially many positive integer values of q via an oracle. p. 3
Where the paper says it

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.

Furthermore, they show that the limit can be computed symbolically in polynomial time as it corresponds simply to the ratio of the leading coefficients. p. 7
Where the paper says it

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.

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

Where the paper says it

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.

They achieve this by constructing a graph HI,q where edges are defined based on the sets Si and elements ui. p. 2
Where the paper says it

In X3C, we are given a collection of sets S := {S1, . , Sn}, each of which consists of 3 elements from a universe U := {u1, .

For linear extensions of height-2 posets, they prove Theorem 1. p. 0
Where the paper says it

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.

4 by showing that counting linear extensions of N-free posets of height 3 is hard. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

The second obstruction for linear extensions of posets of height 2 is that the amplification step creates many copies of the elements ui with the same neighborhood, which can create subgraphs isomorphic to K3,3. p. 1
Where the paper says it

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.

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

Where the paper says it

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].

This research is (partially) supported by the DARPA expMath program through the DARPA CMO contract number HR0011262E028. Initial discussions related to the proofs of Theorem 1. p. 2
Where the paper says it

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.

1 and Theorem 1. p. 1
Where the paper says it

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.

4 were assisted by the use of ChatGPT and Gemini. p. 0
Where the paper says it

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.

All outputs from these models were reviewed and edited by the authors, who take full responsibility for the correctness, originality, and integrity of this manuscript.

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

  1. 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.

  2. 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.

  3. 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).

  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