Generalized Coloring of Permutations

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10378317" target="_blank" >RIV/00216208:11320/18:10378317 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Generalized Coloring of Permutations

Popis výsledku v původním jazyce

A permutation $pi$ is a emph{merge} of a permutation $sigma$ and a permutation $tau$, if we can color the elements of $pi$ red and blue so that the red elements have the same relative order as $sigma$ and the blue ones as~$tau$. We consider, for fixed hereditary permutation classes $cC$ and $cD$, the complexity of determining whether a given permutation $pi$ is a merge of an element of $cC$ with an element of~$cD$. We develop general algorithmic approaches for identifying polynomially tractable cases of merge recognition. Our tools include a version of nondeterministic logspace streaming recognizability of permutations, which we introduce, and a concept of bounded width decomposition, inspired by the work of Ahal and Rabinovich. As a consequence of the general results, we can provide nontrivial examples of tractable permutation merges involving commonly studied permutation classes, such as the class of layered permutations, the class of separable permutations, or the class of permutations avoiding a decreasing sequence of a given length. On the negative side, we obtain a general hardness result which implies, for example, that it is NP-complete to recognize the permutations that can be merged from two subpermutations avoiding the pattern 2413.

Název v anglickém jazyce

Generalized Coloring of Permutations

Popis výsledku anglicky

A permutation $pi$ is a emph{merge} of a permutation $sigma$ and a permutation $tau$, if we can color the elements of $pi$ red and blue so that the red elements have the same relative order as $sigma$ and the blue ones as~$tau$. We consider, for fixed hereditary permutation classes $cC$ and $cD$, the complexity of determining whether a given permutation $pi$ is a merge of an element of $cC$ with an element of~$cD$. We develop general algorithmic approaches for identifying polynomially tractable cases of merge recognition. Our tools include a version of nondeterministic logspace streaming recognizability of permutations, which we introduce, and a concept of bounded width decomposition, inspired by the work of Ahal and Rabinovich. As a consequence of the general results, we can provide nontrivial examples of tractable permutation merges involving commonly studied permutation classes, such as the class of layered permutations, the class of separable permutations, or the class of permutations avoiding a decreasing sequence of a given length. On the negative side, we obtain a general hardness result which implies, for example, that it is NP-complete to recognize the permutations that can be merged from two subpermutations avoiding the pattern 2413.

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í

2018

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

26th Annual European Symposium on Algorithms (ESA 2018)

ISBN

978-3-95977-081-1

ISSN

1868-8969

e-ISSN

neuvedeno

Počet stran výsledku

14

Strana od-do

1-14

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Helsinky, Finsko

Datum konání akce

20. 8. 2018

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

WRD - Celosvětová akce

Kód UT WoS článku

—