Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
summary
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…
In short
The paper proves that counting various graph orderings, such as successive vertex orderings and shellings of bipartite graphs, is computationally hard. They use a technique involving gadget amplification to show that certain counting problems are difficult to solve in polynomial time by relating them to the hardness of exact cover problems.
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 used across episodes
This episode discusses
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit · Paper Radio
- Successive vertex orderings of graphs
- Linear extensions of finite posets
The paper
Hardness of Counting Orderings: Taking Gadget Amplification to the Limit · Read on arXiv
Universidad Catolica de Chile · Carnegie Mellon University
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.
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.
More episodes
- 2411.16152-Optimizing Winograd Convolution on ARMv8 processors
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines