Griddings of Permutations and Hardness of Pattern Matching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10431882" target="_blank" >RIV/00216208:11320/21:10431882 - isvavai.cz</a>

Výsledek na webu

<a href="https://drops.dagstuhl.de/opus/volltexte/2021/14505/" target="_blank" >https://drops.dagstuhl.de/opus/volltexte/2021/14505/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2021.65" target="_blank" >10.4230/LIPIcs.MFCS.2021.65</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Griddings of Permutations and Hardness of Pattern Matching

Popis výsledku v původním jazyce

We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations τ (the &quot;text&quot;) and π (the &quot;pattern&quot;), and the goal is to decide whether τ contains π as a subpermutation. On general inputs, PPM is known to be NP-complete by a result of Bose, Buss and Lubiw. In this paper, we focus on restricted instances of PPM where the text is assumed to avoid a fixed (small) pattern σ; this restriction is known as Av(σ)-PPM. It has been previously shown that Av(σ)-PPM is polynomial for any σ of size at most 3, while it is NP-hard for any σ containing a monotone subsequence of length four. In this paper, we present a new hardness reduction which allows us to show, in a uniform way, that Av(σ)-PPM is hard for every σ of size at least 6, for every σ of size 5 except the symmetry class of 41352, as well as for every σ symmetric to one of the three permutations 4321, 4312 and 4231. Moreover, assuming the exponential time hypothesis, none of these hard cases of Av(σ)-PPM can be solved in time 2^o(n/log n). Previously, such conditional lower bound was not known even for the unconstrained PPM problem. On the tractability side, we combine the CSP approach of Guillemot and Marx with the structural results of Huczynska and Vatter to show that for any monotone-griddable permutation class ????, PPM is polynomial when the text is restricted to a permutation from ????.

Název v anglickém jazyce

Griddings of Permutations and Hardness of Pattern Matching

Popis výsledku anglicky

We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations τ (the &quot;text&quot;) and π (the &quot;pattern&quot;), and the goal is to decide whether τ contains π as a subpermutation. On general inputs, PPM is known to be NP-complete by a result of Bose, Buss and Lubiw. In this paper, we focus on restricted instances of PPM where the text is assumed to avoid a fixed (small) pattern σ; this restriction is known as Av(σ)-PPM. It has been previously shown that Av(σ)-PPM is polynomial for any σ of size at most 3, while it is NP-hard for any σ containing a monotone subsequence of length four. In this paper, we present a new hardness reduction which allows us to show, in a uniform way, that Av(σ)-PPM is hard for every σ of size at least 6, for every σ of size 5 except the symmetry class of 41352, as well as for every σ symmetric to one of the three permutations 4321, 4312 and 4231. Moreover, assuming the exponential time hypothesis, none of these hard cases of Av(σ)-PPM can be solved in time 2^o(n/log n). Previously, such conditional lower bound was not known even for the unconstrained PPM problem. On the tractability side, we combine the CSP approach of Guillemot and Marx with the structural results of Huczynska and Vatter to show that for any monotone-griddable permutation class ????, PPM is polynomial when the text is restricted to a permutation from ????.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA18-19158S" target="_blank" >GA18-19158S: Algoritmické, strukturální a složitostní aspekty geometrických a dalších konfigurací</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

ISBN

978-3-95977-201-3

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

22

Strana od-do

1-22

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum für Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Tallinn, Estonsko

Datum konání akce

23. 8. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—