Subexponential pattern matching for permutations avoiding a fixed pattern
Let be a text permutation of length , let be a pattern permutation, and let be an arbitrary permutation of length . Suppose that avoids .
Fixed-pattern avoidance conjecture. The permutation pattern matching problem with text and pattern can be solved in time .
This conjecture would unify and generalize several subexponential algorithms for restricted families of permutations. The source states that characterizing the base of the Stanley–Wilf bound remains a deep open question, and presents this as a natural open direction.
References
- László Kozma, “Faster and simpler algorithms for finding large patterns in permutations”, arXiv:1902.08809 (2019).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.