Inclusion relationships among permutation problems (Q1106217)

Let \(X=\{x_ 1,...,x_ n\}\) be a set of n elements. A permutation problem on X is a decision problem in NP which consists of determining whether there exists an n element permutation satisfying a set of ordering constraints expressed as collections of permutations of at most k elements of X. Several well-known NP-complete problems such as cyclic ordering, betweenness, and serializability can be expressed as permutation problems. If we consider symbol preserving polynomial reductions, i.e., reductions that do not make use of additional elements, strict inclusion relationships among permutation problems can be proved. In particular, the serializability problem is shown to be included in the deadlock avoidance one.