On the Complexity of Counting Orderings In Graphs
Marcelo Arenas 1,2 and María Alejandra Schild 1,2, Bernardo Subercaseaux 3 · 2026
Read On the Complexity of Counting Orderings In Graphs by Marcelo Arenas 1,2 and María Alejandra Schild 1,2, Bernardo Subercaseaux 3 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29157.txt.
Introduction
Arenas, Schild and Subercaseaux settle the computational complexity of several problems that count orderings of a graph's vertices or edges under adjacency constraints. Counting such orderings exactly is typically hard, and they prove each problem complete for the counting class #P, the standard benchmark of counting hardness. All the proofs run through one new common technique.
They build a family of instances controlled by a parameter that amplifies a simple gadget. After multiplying by a stated factor, the values agree with a rational function of the parameter, whose numerator and denominator can be recovered in polynomial time. Evaluating that function in symbols at a limiting value recovers a known hard function. The technique proves hardness for vertex orderings of bipartite graphs, st-numberings, shellings of bipartite graphs, and linear extensions of two families of posets. One result settles a 2015 conjecture of Felsner and Manneville about height-three posets.
Catalog record
| CREATOR | Marcelo Arenas 1,2 and María Alejandra Schild 1,2, Bernardo Subercaseaux 3 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29157
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Complexity of Counting Orderings In Graphs Marcelo Arenas 1,2 and María Alejandra Schild 1,2, Bernardo Subercaseaux 3 Abstract . We study the computational complexity of several counting problems on graphs. Each of them consists of counting orderings of the vertices or edges with adjacency constraints. We show # 𝖯 \#\mathsf{P} -completeness for all of them via a common new technique. Given a counting function C C of interest, we define a parameterized family of instances G q G_{q} , where the parameter q q controls the amplification of a simple gadget. After multiplying by an explicit factor f ( q ) f(q) , we show that the values of f ( q ) ⋅ C ( G q ) f(q)\cdot C(G_{q}) , for positive integers q q , agree with a rational function in q q whose numerator and denominator can be interpolated in polynomial time. We then recover a # 𝖯 \#\mathsf{P} -hard function by evaluating this rational function symbolically at a limiting value L ∈ ℚ ∪ { ∞ , − ∞ } L\in\mathbb{Q}\cup\{\infty,-\infty\} . With this methodology, we show # 𝖯 \#\mathsf{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 3 , and (e) linear extensions of posets of height 2 2 . Result (d) settles a conjecture of Felsner and Manneville (2015). Although result (e) 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. 1. Introduction Many combinatorial structures can be constructed by adding their elements one at a time, subject only to local incidence constraints. In this paper, we show that several counting problems about such orderings are intractable, even for restricted classes of graphs. We cover the four natural variants obtained by independently choosing whether the objects to be ordered are vertices or edges, and whether the underlying graph is undirected or directed. We prove \#\mathsf{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 \#\mathsf{P} is immediate, so we indeed obtain \#\mathsf{P} -completeness for all of them. 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. To the best of our knowledge, this method provides a novel application of rational interpolation in counting complexity. We start by defining the problems. Given an undirected graph G=(V,E) on n vertices, a successive vertex ordering (SVO) of G is an ordering (v_{1},\dots,v_{n}) of its vertices such that for each 2\leqslant i\leqslant n , vertex v_{i} is adjacent to some v_{j} with j<i . Equivalently, an ordering (v_{1},\dots,v_{n}) is an SVO if the induced subgraph G[\{v_{1},\ldots,v_{i}\}] is connected for every 1\leqslant i\leqslant n . Counting successive vertex orderings has been studied both for specific classes of graphs via explicit formulas [ 5 ] and for general graphs, where an O(n2^{n}) counting algorithm was recently devised by Agrawal, Erturk, and Louis [ 1 ] . Our first result is that we should not expect much more efficient algorithms. Theorem 1.1 . \#\mathsf{SVO} is \#\mathsf{P} -complete, with hardness already for bipartite graphs. The notion of SVOs is tightly related to that of shellings of a graph: orderings (e_{1},\dots,e_{m}) of the edges such that for each i>1 , the edge e_{i} intersects some prior edge e_{j} with j<i . Indeed, it is easy to see that each shelling of a graph G is in natural correspondence with an SVO of the line graph of G . Once again, the number of shellings has been studied for specific classes such as trees and complete bipartite graphs [ 7 ] . Further results on shellings of graphs were presented in the master’s thesis of the second author [ 11 ] . We answer the main question posed in that thesis. Theorem 1.2 . \#\mathsf{Shellings} is \#\mathsf{P} -complete, with hardness already for bipartite graphs. In 2018, Goaoc, Paták, Patáková, Tancer, and Wagner settled a long-standing open question by showing that deciding whether a d -dimensional simplicial complex is “shellable” is \mathsf{NP} -complete for d\geqslant 2 [ 8 ] . Since 1 -dimensional simplicial complexes are just graphs, 1.2 shows that while the decision problem is easy for d=1 , its counting variant is already hard. The \#\mathsf{P} -hardness automatically propagates to the higher-dimensional variants, as we can lift the dimension of a simplicial complex by taking a cone over a new vertex while keeping its number of shellings unchanged. We note that the proof of \mathsf{NP} -completeness presented in [ 8 ] does not provide \#\mathsf{P} -hardness directly, as the reduction uses existential arguments that are not counting-preserving. As an immediate consequence of our proof for 1.1 , we obtain \#\mathsf{P} -hardness for counting st -numberings of a graph, a well-studied notion with applications to, e.g., computational geometry [ 10 ] . Given a graph G and vertices s,t\in V(G) , an st -numbering of G is an ordering (v_{1},v_{2},\dots,v_{n-1},v_{n}) of its vertices such that v_{1}=s , v_{n}=t , and for each 2\leqslant i\leqslant n-1 vertex v_{i} is both adjacent to some v_{j} with j<i and to some v_{k} with k>i . Corollary 1.3 . Given G and vertices s and t , it is \#\mathsf{P} -complete to count the st -numberings of G . Finally, we turn our attention to the well-studied problem of counting linear extensions of posets. A linear extension of a poset (P,\preceq) is a total ordering \leqslant of P such that whenever p_{i}\preceq p_{j} , it follows that p_{i}\leqslant p_{j} . Viewing the poset as a directed graph D=(V,E) , a linear extension is an ordering (v_{1},\dots,v_{n}) of its vertices such that for every v_{i} , all the in-neighbors of v_{i} appear before v_{i} . The \#\mathsf{P} -hardness of counting linear extensions for general posets was proved by Brightwell and Winkler [ 2 ] , who left as an open problem whether hardness held already for posets of height 2 . This long-standing question was finally settled in the affirmative by Dittmer and Pak [ 4 ] . Our proof technique yields two further consequences for this problem. First, it gives an alternative proof of \#\mathsf{P} -hardness for posets of height 2 . The core of the argument is a duality between rooted SVOs and linear extensions: in an SVO, for a vertex v to appear in a given position i>1 , it is required that some neighbor of v appears before position i , whereas for linear extensions it is required that all in-neighbors of v appear before position i . An illustration of this duality is presented in Figure 1.1 — Figure 1(a) presents an undirected graph over which we want to count SVOs that start at root