Enumeration Complexity of Permutation Classes
cs.CC, math.CO
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study classes of permutations that are defined by avoidance of forbidden patterns.
Abstract
We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set B of forbidden patterns, we study the avoider enumeration problem: given an integer n, output all B-avoiding permutations of length n. Avoider enumeration is output-polynomial for every fixed B. However, our main notion of efficiency is polynomial delay. We use the insert-maximum tree as a search tree, in which permutations are built by repeatedly inserting a new maximum while preserving pattern avoidance. This leads to the insert-maximum extension problem, which asks if a given permutation has an avoiding descendant at a specified depth. An algorithm for this problem can prune branches that cannot reach the target length. Hence, if this problem is in P, we obtain polynomial-delay enumeration. To investigate this problem, we introduce and study pockets, the maximal finite subtrees of the insert-maximum tree. For fixed B, if there is a polynomial p such that every pocket rooted at ρ has at most p(ρ) nodes, then the extension problem is solvable in polynomial time and enumeration has polynomial delay. In particular, a bound on pocket depth depending only on B suffices. We prove such a bound if the class is well-quasi-ordered, has a regular insertion encoding, or if B omits one of the three maximum-position types: leftmost, interior, or rightmost. We also prove that extension is in NP for every fixed B, even with binary-encoded target depth. On the negative side, we construct a fixed set of 55 forbidden patterns for which extension is NP-complete. Consequently, enumerating valid extensions from a given starting permutation cannot have polynomial delay unless P=NP. This also answers a question of Hanika by showing that the forbidden permutation constraint satisfaction problem can be NP-complete for a fixed forbidden set.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- 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?