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 subsequences of $\tau$ that have the same relative order as $\pi$. A simple brute-force approach solves #PPM for a pattern of length $k$ and a text of length $n$ in time $O(n^{ k+1})$, while Berendsohn, Kozma and Marx have recently shown that under the exponential time hypothesis (ETH), it cannot be solved in time $f(k) n^{ o(k/\log k)}$ for any function $f$. In this paper, we consider the restriction of #PPM, known as $\mathcal{ C}$-Pattern #PPM, where the pattern $\pi$ must belong to a hereditary permutation class $\mathcal{ C}$. Our goal is to identify the structural properties of $\mathcal{ C}$ that determine the complexity of $\mathcal{ C}$-Pattern #PPM. We focus on two such structural properties, known as the long path property (LPP) and the deep tree property (DTP). Assuming ETH, we obtain these results: 1. If $C$ has the LPP, then $\mathcal{ C}$-Pattern #PPM cannot be solved in time $f(k)n^{ o(\sqrt{ k})}$ for any function $f$, and 2. if $C$ has the DTP, then $\mathcal{ C}$-Pattern #PPM cannot be solved in time $f(k)n^{ o(k/\log^2 k)}$ for any function $f$. Furthermore, when $\mathcal{ C}$ is one of the so-called monotone grid classes, we show that if $\mathcal{ C}$ has the LPP but not the DTP, then $\mathcal{ C}$-Pattern #PPM can be solved in time $f(k)n^{ O(\sqrt k)}$. In particular, the lower bounds above are tight up to the polylog terms in the exponents.
Categories: cs.CC cs.DM