Enumeration Complexity of Permutation Classes
In the authors' words
We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set of forbidden patterns, we study the avoider enumeration problem: given an integer , output all -avoiding permutations of length . Avoider enumeration is output-polynomial for every fixed . 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 , if there is a polynomial such that every pocket rooted at has at most 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 suffices. We prove such a bound if the class is well-quasi-ordered, has a regular insertion encoding, or if omits one of the three maximum-position types: leftmost, interior, or rightmost. We also prove that extension is in NP for every fixed , even with binary-encoded target depth. On the negative side, we construct a fixed set of 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.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.