License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.22
URN: urn:nbn:de:0030-drops-154050
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15405/
Jelínek, Vít ;
Opler, Michal ;
Pekárek, Jakub
Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder
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 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 ? 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 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.
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 Pattern-Counting Hard, and Deep Trees Make It Harder}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {22:1--22:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-216-7},
ISSN = {1868-8969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15405},
URN = {urn:nbn:de:0030-drops-154050},
doi = {10.4230/LIPIcs.IPEC.2021.22},
annote = {Keywords: Permutation pattern matching, subexponential algorithm, conditional lower bounds, tree-width}
}
|
Keywords: |
|
Permutation pattern matching, subexponential algorithm, conditional lower bounds, tree-width |
|
Collection: |
|
16th International Symposium on Parameterized and Exact Computation (IPEC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
22.11.2021 |
