Enumeration Complexity of Permutation Classes

arXiv:2610.37940 · cs.CC, math.CO · Submitted 2026-10-27 · Read on arXiv

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