Permutations avec sous-séquences interdites

Soit le jeu et C (n, k) le jeu de toutes les -combinaisons d'éléments de sans répétition. Soit un -uple dans . On dit qu'une permutation de l'ensemble évite s'il n'y a pas de k-tuple d'entiers tels que { 1 , . . . , n } k [ n ] p = p 1 p 2 . . . p k k C ( n , k ) π : [ n ] → [ n ] [ n ] p i 1 < i 2 < . . . < i k π $[n]$$\{1,...,n\}$$k$$[n]$$p= p_1p_2...p_k$$k$$C(n,k)$$\pi:[n]\rightarrow [n]$$[n]$$p$$i_1<i_2<...<i_k$

Par exemple, si la permutation évite comme sous-séquence, contrairement à la permutation .12453 134 1 2 3 5 $n=5$$12453$$134$$\mathbf{1}2\mathbf{3}5\mathbf{4}$

Question: Soit une constante. Etant donné un ensemble de - uplets, trouver une permutation qui évite chaque k uplet dans S . S ⊂ C ( n , k ) k π : [ n ] → [ n ] k $k$$S\subset C(n,k)$$k$$\pi:[n]\rightarrow [n]$$k$$S$

1. Existe-t-il un algorithme pour ce problème qui est polynomial dans $|P|$et $n$ ? Ici $n$ est donné en unaire. Un algorithme fonctionnant dans le temps $n^{f(k)}|P|^{g(k)}$ conviendrait.
2. Ou ce problème est-il NP-complet?

Toutes les références à ce problème ou suggestions d'algorithmes sont les bienvenues. Notez que la notion de permutation évitant la sous-séquence définie ci-dessus n'est pas la même que la notion de permutation évitant le motif où seul l'ordre relatif des éléments est important, et qui semble bien étudié en combinatoire.

Il est NP-complet pour par une réduction de l' interdépendance . Dans le problème d'interdépendance, on donne éléments à ordonner totalement, et des contraintes sur certains triplets d'articles forcent un élément du triple à être entre les deux autres. Dans votre problème, la même contrainte peut être forcée en interdisant toutes les sous-séquences sur trois éléments qui ne placent pas l'élément central au milieu. Mais l'interdépendance est connue pour être NP-complète: voir J. Opatrny, Total ordering problem, SIAM J. Comput. , 8 (1979), p. 111-114.$k=3$$n$