Permutaciones con subsecuencias prohibidas

Supongamos que denota el conjunto y C (n, k) denota el conjunto de todas las combinaciones de elementos de sin repetición. Supongamos que sea ​​una -tupla en . Decimos que una permutación del conjunto evita si no hay k-tupla de enteros tal que $[n]$k [ n ] p = p 1 p 2 . . . p k k C ( n , k ) π : [ n ] → [ n ] [ n ] p i 1 < i 2 < . . . < i k π ( i 1$\{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$

Por ejemplo, si entonces la permutación evita como subsecuencia, mientras que la permutación no lo hace.$n=5$$12453$$134$$\mathbf{1}2\mathbf{3}5\mathbf{4}$

Pregunta: Sea una constante. Dado un conjunto de -tuplas, encontrar una permutación que evita cada tupla en . $k$$S\subset C(n,k)$$k$$\pi:[n]\rightarrow [n]$$k$$S$

1. ¿Existe un algoritmo para este problema que sea polinómico eny ? Aquí se da en unario. Un algoritmo que se ejecuta en el tiempo estaría bien.n n n f ( k ) | P | g ( k $|P|$$n$$n$$n^{f(k)}|P|^{g(k)}$
2. ¿O es este problema NP-completo?

Cualquier referencia para este problema, o sugerencias de algoritmos son bienvenidas. Tenga en cuenta que la noción de permutación que evita la subsecuencia definida anteriormente no es la misma que la noción de patrón de permutación donde solo es importante el orden relativo de los elementos, y que parece estar bien estudiado en combinatoria.

Es NP-completo para por una reducción de entremedio . En el problema de intermediación, uno recibe n elementos para que estén totalmente ordenados, y las restricciones sobre algunos triples de elementos obligan a un elemento del triple a estar entre los otros dos. En su problema, se puede forzar la misma restricción al prohibir todas las subsecuencias en tres elementos que no colocan el elemento medio en el medio. Pero se sabe que la intermediación es NP completa: ver J. Opatrny, Total ordering problem, SIAM J. Comput. , 8 (1979), págs. 111-114.$k=3$$n$