Long paths make pattern-counting hard, and deep trees make it harder

Vít Jelínek, Michal Opler, Jakub Pekárek

We study the counting problem known as #PPM, whose input is a pair of permutations $\pi$ and $\tau$ (called pattern and text, respectively), and the task is to find the number of subseq…