کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428876 686953 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kernelization lower bound for Permutation Pattern Matching
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Kernelization lower bound for Permutation Pattern Matching
چکیده انگلیسی


• 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 5, May 2015, Pages 527–531
نویسندگان
, , , ,