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.CPM.2022.21
URN: urn:nbn:de:0030-drops-161481
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16148/
Bulteau, Laurent ;
Fertin, Guillaume ;
Jugé, Vincent ;
Vialette, Stéphane
Permutation Pattern Matching for Doubly Partially Ordered Patterns
Abstract
We study in this paper the Doubly Partially Ordered Pattern Matching (or DPOP Matching) problem, a natural extension of the Permutation Pattern Matching problem. Permutation Pattern Matching takes as input two permutations σ and π, and asks whether there exists an occurrence of σ in π; whereas DPOP Matching takes two partial orders P_v and P_p defined on the same set X and a permutation π, and asks whether there exist |X| elements in π whose values (resp., positions) are in accordance with P_v (resp., P_p). Posets P_v and P_p aim at relaxing the conditions formerly imposed by the permutation σ, since σ yields a total order on both positions and values. Our problem being NP-hard in general (as Permutation Pattern Matching is), we consider restrictions on several parameters/properties of the input, e.g., bounding the size of the pattern, assuming symmetry of the posets (i.e., P_v and P_p are identical), assuming that one partial order is a total (resp., weak) order, bounding the length of the longest chain/anti-chain in the posets, or forbidding specific patterns in π. For each such restriction, we provide results which together give a(n almost) complete landscape for the algorithmic complexity of the problem.
BibTeX - Entry
@InProceedings{bulteau_et_al:LIPIcs.CPM.2022.21,
author = {Bulteau, Laurent and Fertin, Guillaume and Jug\'{e}, Vincent and Vialette, St\'{e}phane},
title = {{Permutation Pattern Matching for Doubly Partially Ordered Patterns}},
booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
pages = {21:1--21:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-234-1},
ISSN = {1868-8969},
year = {2022},
volume = {223},
editor = {Bannai, Hideo and Holub, Jan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16148},
URN = {urn:nbn:de:0030-drops-161481},
doi = {10.4230/LIPIcs.CPM.2022.21},
annote = {Keywords: Partial orders, Permutations, Pattern Matching, Algorithmic Complexity, Parameterized Complexity}
}
|
Keywords: |
|
Partial orders, Permutations, Pattern Matching, Algorithmic Complexity, Parameterized Complexity |
|
Collection: |
|
33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.06.2022 |
