A W[1]-Completeness Result for Generalized Permutation Pattern Matching

Details A W[1]-Completeness Result for Generalized Permutation Pattern Matching A W[1]-Completeness Result for Generalized Permutation Pattern Matching

2011-09-09

arxiv.org/abs/1109.1951v3

Computer Science

Computational Complexity

11 pages

Scientific paper

The NP-complete Permutation Pattern Matching problem asks whether a permutation P (the pattern) can be matched into a permutation T (the text). A matching is an order-preserving embedding of P into T. In the Generalized Permutation Pattern Matching problem one can additionally enforce that certain adjacent elements in the pattern must be mapped to adjacent elements in the text. This paper studies the parameterized complexity of this more general problem. We show W[1]-completeness with respect to the length of the pattern P. Under standard complexity theoretic assumptions this implies that no fixed-parameter tractable algorithm can be found for any parameter depending solely on P.

Affiliated with

Also associated with

No associations

Rating

A W[1]-Completeness Result for Generalized Permutation Pattern Matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A W[1]-Completeness Result for Generalized Permutation Pattern Matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A W[1]-Completeness Result for Generalized Permutation Pattern Matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-413329