Project topics and materials
Get Complete Project Material File(s) Now! »
When a Problem is NP-Complete
Solutions exist whenever we need to solve an instance of an NP-Complete problem.
In practice, not every instance can appear and we use this to our advantage.
An extreme case to consider is whether there is a nite number of instances; in that case, one can consider computing every instance (if temporally possible) and keeping the solutions somewhere. Another case to consider, is whether the instances have constraints; in that case, the constraints may allow to compute a solution faster than a general instance. This case can be illustrated with the problem of sorting a sequence of numbers. This problem is known to be solvable in O(n log n) time and constant space memory, where n is the size of the sequence for any sequence. However this problem is solved by the counting sort algorithm, which solves this problem in O(mn) time where m is the maximal value and n is the size of the sequence but in O(m) space. So, if we we give the constraint for the maximal element to be lower than log n, the latter algorithm is the best algorithm.
Another possibility is the class of Fixed Parameter Tractable (noted FPT) problems. The class of FPT problems is a subclass of the NP-complete problems. A problem is FPT if its input can be split into two parts and can be solved in exponential time by the size of the rst part of the input while polynomial time by the size of the second part of the input. When a problem is FPT, one can hope for a practical algorithm; indeed, if the rst part of the input is known to be always very small then even if the algorithm is exponential, the algorithm would still be runnable in human time. There exist others classes of NP-Complete problems other than the class of FPT problems. A notable hierarchy of class is the W-hierarchy (formed by the classes W[1], W[2], : : :). These classes are used to represent how hard it is to check whether an answer is a solution to a problem.
The Relation With This Thesis
The main problem studied in this thesis is NP-Complete. The goal of this section was to examine the intuition that using brute force to solve an instance of the problem may not be the best solution. We refer the reader to [21] We adopted the rst point of the above paragraph, adding constraints to the input to dene classes and nd a polynomial algorithm to solve the problem for this class.
A Subsequence of a Permutation
It is useful to consider only part of a permutation. To do so, we are allowed to remove elements of that permutation. For instance, in the permutation 52143, one may want to consider only the elements with a value above 1; intuitively, the subsequence permutation is 5243. Formally speaking, a subsequence of a permutation is any permutation that can be obtained from by deleting some elements without changing the linear order of the remaining elements. Note that when subsequences of a permutation are being discussed, « of a permutation » is omitted.
Reduction of a Permutation
The set of a permutation is not always the set f1; 2; : : : ; ng. For example, the permutation given by the images of a mapping and the permutation given by a rectangle are permutations over a set which is not the rst integers. We can also imagine a permutation over any set, as long as we have a linear order over this set. We called those permutations « non-canonical ».
The rst case of non-canonical permutations described above turns out to be a problem: When reading the permutation from left to right, we cannot guess the relative order (in the linear order by value) of an element until we read all of the elements. For example, in the permutation 91645, we cannot know that 6 is the second largest element from having read 916.
It should also be noted that we only need the linear order between the value of the elements. So the actual values of the elements do not matter as long as this linear order is preserved.
It is in our best interest to work with a canonical permutation, that is a permutation of size n with domain f1; 2; : : : ; ng. As we do many operations on a permutation, it is better to spend some time computing a permutation that is easy to handle and understand rather than using a « hard » permutation and spending time to make operations on it. We call the operation that goes from a non-canonical permutation to an canonical permutation a reduction.
Table of contents :
1 Introduction
2 Context of the Thesis
2.1 Non-deterministic Polynomial Problem
2.1.1 The Notion of Problem
2.1.2 Reduction: Transforming one Problem into Another
2.1.3 The Classes of Problems
2.1.4 When a Problem is NP-Complete
2.1.5 The Relation With This Thesis
3 Denitions
3.1 Permutations
3.1.1 Denitions for Permutation
3.1.2 The Representation of a Permutation.
3.1.3 Comparing the Elements of a Permutation
3.1.4 A Subsequence of a Permutation
3.1.5 Elements of a Subsequence
3.2 Operations on Permutation
3.2.1 Transforming a Permutation
3.2.2 Mapping
3.2.3 Reduction of a Permutation
3.2.4 Direct Sums and Skew Sums
3.3 The Notions of Occurrence and Avoidance
3.3.1 Order isomorphism
3.3.2 An Occurrence
3.4 Set of Pattern Avoidance
3.4.1 Denition
3.4.2 The Utilities of Classes of Permutation
3.4.3 Comparing Avoiding Sets
3.5 The Permutation Pattern Matching Problem
3.5.1 The Permutation Pattern Matching Problem
3.5.2 The Permutation Bivincular Pattern Matching Problem .
4 The Permutation Pattern Matching Problem Paradigm
4.1 General Case of the Problem
4.2 Adding Constraints to the Permutation Pattern Matching Problem
4.3 The Permutation Pattern Matching Problem with Specic Classes of Permutations
4.3.1 Separable Permutations
4.3.2 Increasing Permutations
4.3.3 321-Avoiding Permutations
4.3.4 Skew-Merged Permutations
4.3.5 The Case of Fixed Permutations
4.3.6 Wedge Permutations
4.4 Generalisation of Patterns
4.4.1 Complexity with Mesh or Bivincular Patterns
4.4.2 Consecutive Pattern
4.4.3 Boxed Mesh Pattern
4.5 State of the Art
4.6 Point of View of this Thesis
5 Related problems
5.1 Longest Subsequence
5.1.1 Longest Increasing Subsequence
5.1.2 Longest Alternating Subsequence
5.1.3 State of the Art
5.2 Longest Common Subsequence
5.2.1 Longest Common Subsequence for Words
5.2.2 Longest Common Subsequence for Permutations.
5.2.3 Restricting the Set to the Set of Permutations that are in Bijection with Binary Words
5.2.4 Restricting the Set to the Permutations Separable Permutations
5.2.5 Computing the Longest Wedge Subsequence
5.2.6 State of the Art
5.3 Superpattern
5.3.1 Lower and Upper Bounds for the size of the Minimal Superpattern for all Permutations of the same Size
5.3.2 Superpattern for Rie-Shue Permutations
5.3.3 Superpattern for 321-Avoiding Permutations
5.3.4 Superpattern for 213-Avoiding Permutations
5.3.5 State of the Art
5.4 Shue
5.4.1 Word Shues
5.4.2 Shue for Permutations
5.4.3 Recognising the Shue of two Separable Permutations
5.4.4 State of the Art
6 Separable Permutations
6.1 The Structure of Separable Permutations
6.1.1 Substitution Decomposition
6.1.2 Separable Permutations Seen as a Direct or Skew Sum
6.1.3 Binary Trees
6.1.4 A Separable Permutations Seen as a Tree
6.1.5 Computing the Tree of a Separable Permutation
6.1.6 Relations Between the Decomposition in Direct and Skew Sums and the Separable Tree
6.2 Detecting a Separable Pattern
6.2.1 Simple Algorithm
6.2.2 Algorithm of Ibarra
6.2.3 Improved Version of Ibarra
6.3 Both and are Separable Permutations
6.3.1 Best algorithm so far
6.3.2 Our Solution
6.4 Deciding the Union of a Separable Permutation
6.5 Finding a Maximum Size Separable Subpermutation
6.6 Vincular and Bivincular Separable Patterns
7 Wedge Permutations
7.1 Structure of a Wedge Permutation
7.1.1 General Structure.
7.1.2 Bijection with Binary Words
7.1.3 Decomposition of a Wedge Permutations into Factors
7.2 Both and are Wedge Permutations
7.3 Only is a Wedge Permutation
7.3.1 A Simple Algorithm
7.3.2 Improving the Simple Algorithm
7.4 Bivincular Wedge Permutation Patterns
7.5 Computing the Longest Wedge Permutation Pattern
8 Conclusion
