Long paths make pattern-counting hard, and deep trees make it harder
share
We study the counting problem known as #PPM, whose input is a pair of permutations π and τ (called pattern and text, respectively), and the task is to find the number of subsequences of τ that have the same relative order as π. 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 𝒞-Pattern #PPM, where the pattern π must belong to a hereditary permutation class 𝒞. Our goal is to identify the structural properties of 𝒞 that determine the complexity of 𝒞-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 𝒞-Pattern #PPM cannot be solved in time f(k)n^o(√(k)) for any function f, and 2. if C has the DTP, then 𝒞-Pattern #PPM cannot be solved in time f(k)n^o(k/log^2 k) for any function f. Furthermore, when 𝒞 is one of the so-called monotone grid classes, we show that if 𝒞 has the LPP but not the DTP, then 𝒞-Pattern #PPM can be solved in time f(k)n^O(√(k)). In particular, the lower bounds above are tight up to the polylog terms in the exponents.
READ FULL TEXT