Name
Abstract | ||
|---|---|---|
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 / poly ) by introducing a new polynomial reduction from the clique problem to permutation pattern matching. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.ipl.2015.01.001 | Information Processing Letters |
Keywords | Field | DocType |
parameterized complexity,algorithms | Permutation graph,Discrete mathematics,Combinatorics,Permutation matrix,Cyclic permutation,Random permutation,Bit-reversal permutation,Permutation pattern,Generalized permutation matrix,Partial permutation,Mathematics | Journal |
Volume | Issue | ISSN |
115 | 5 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ivan Bliznets | 1 | 13 | 2.99 |
| Marek Cygan | 2 | 556 | 40.52 |
| Paweł Komosa | 3 | 0 | 1.35 |
| Lukáš Mach | 4 | 23 | 3.03 |