Jelínek, Vít ;
Opler, Michal ;
Valtr, Pavel
Generalized Coloring of Permutations
Abstract
A permutation pi is a 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 C and D, the complexity of determining whether a given permutation pi is a merge of an element of C with an element of D.
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 NPcomplete to recognize the permutations that can be merged from two subpermutations avoiding the pattern 2413.
BibTeX  Entry
@InProceedings{jelnek_et_al:LIPIcs:2018:9513,
author = {V{\'i}t Jel{\'i}nek and Michal Opler and Pavel Valtr},
title = {{Generalized Coloring of Permutations}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {50:150:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9513},
URN = {urn:nbn:de:0030drops95137},
doi = {10.4230/LIPIcs.ESA.2018.50},
annote = {Keywords: Permutations, merge, generalized coloring}
}
2018
Keywords: 

Permutations, merge, generalized coloring 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 