Abstract
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 bruteforce 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 𝒞 has the LPP, then 𝒞Pattern #PPM cannot be solved in time f(k)n^{o(√k)} for any function f, and
2) if 𝒞 has the DTP, then 𝒞Pattern #PPM cannot be solved in time f(k)n^{o(k/log² k)} for any function f.
Furthermore, when 𝒞 is one of the socalled 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.
BibTeX  Entry
@InProceedings{jelinek_et_al:LIPIcs.IPEC.2021.22,
author = {Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Pek\'{a}rek, Jakub},
title = {{Long Paths Make PatternCounting Hard, and Deep Trees Make It Harder}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {22:122:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15405},
URN = {urn:nbn:de:0030drops154050},
doi = {10.4230/LIPIcs.IPEC.2021.22},
annote = {Keywords: Permutation pattern matching, subexponential algorithm, conditional lower bounds, treewidth}
}
Keywords: 

Permutation pattern matching, subexponential algorithm, conditional lower bounds, treewidth 
Collection: 

16th International Symposium on Parameterized and Exact Computation (IPEC 2021) 
Issue Date: 

2021 
Date of publication: 

22.11.2021 