2021/11/05 by Jelínek, Vít, Opler, Michal, Pekárek, Jakub · 1 citation
#05-08 (Primary) 68Q17 #68R15 (Secondary) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2111.03479
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(nk+1), while Berendsohn, Kozma and Marx have recently shown that under the exponential time hypothesis (ETH), it cannot be solved in time f(k) no(k/log k) for any function f. In this paper, we consider the restriction of #PPM, known as C-Pattern #PPM, where the pattern π must belong to a hereditary permutation class C. Our goal is to identify the structural properties of C that determine the complexity of 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 C-Pattern #PPM cannot be solved in time f(k)no(√(k)) for any function f, and 2. if C has the DTP, then C-Pattern #PPM cannot be solved in time f(k)no(k/log2 k) for any function f. Furthermore, when C is one of the so-called monotone grid classes, we show that if C has the LPP but not the DTP, then C-Pattern #PPM can be solved in time f(k)nO(√ k). In particular, the lower bounds above are tight up to the polylog terms in the exponents.