Hanika’s forbidden permutation constraint satisfaction problem question
For every fixed finite set of forbidden permutation patterns, does there exist an algorithm that, given a -avoiding permutation and an integer , enumerates with polynomial delay all -avoiding permutations of length that are descendants of in the insert-maximum tree, where each step inserts a new maximum while preserving -avoidance?
References
- Enumeration Complexity of Permutation Classes — arXiv — Manuel Bodirsky, Mohamed Elsheikh
Source: arXiv
Progress summary
An unrefereed preprint finds both efficient enumeration in several cases and an NP-complete obstruction for one fixed forbidden-pattern constraint, so the general question is not uniformly tractable.
Hanika’s question concerns enumerating permutations avoiding a fixed set of forbidden patterns, particularly whether extensions can always be enumerated with polynomial delay.
October 2026 preprint
Manuel Bodirsky and Mohamed Elsheikh prove polynomial-delay enumeration under several structural conditions, but exhibit a fixed forbidden-pattern set whose extension problem is NP-complete. Thus polynomial-delay enumeration cannot hold in full generality unless . The result is reported only from an unrefereed preprint.
Current status (as of October 2026): The preprint claims substantial partial progress and a conditional obstruction, but the general question remains open and the claims are unverified.
Sources
Solutions 0
No solutions have been posted yet.