کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428876 | 686953 | 2015 | 5 صفحه PDF | دانلود رایگان |

• We prove that the Permutation Pattern Matching problem does not have a polynomial kernel (assuming a widely believed hypothesis from theory of computational complexity).
• A novel polynomial reduction from the Clique problem to the Permutation Pattern Matching problem is introduced.
• The standard cross-composition framework is applied to yield polynomial lower bounds.
A permutation π contains a permutation σ as a pattern if it contains a subsequence of length |σ||σ| whose elements are in the same relative order as in the permutation σ . This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption NP⊈co-NP/polyNP⊈co-NP/poly) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.
Journal: Information Processing Letters - Volume 115, Issue 5, May 2015, Pages 527–531