← All problems

Hanika’s forbidden permutation constraint satisfaction problem question

For every fixed finite set BB of forbidden permutation patterns, does there exist an algorithm that, given a BB-avoiding permutation ρ\rho and an integer n≥∣ρ∣n\ge |\rho|, enumerates with polynomial delay all BB-avoiding permutations of length nn that are descendants of ρ\rho in the insert-maximum tree, where each step inserts a new maximum while preserving BB-avoidance?

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 P=NP\mathrm{P}=\mathrm{NP}. 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.