Перестановки с запрещенными подпоследовательностями

Обозначим через множество а через C (n, k) - множество всех комбинаций элементов из без повторения. Пусть - k- кортеж в C (n, k) . Мы говорим, что перестановка \ pi: [n] \ rightarrow [n] из набора [n] избегает p, если нет k-кортежа целых чисел i_1 <i_2 <... <i_k, такого что \ pi (i_1) = p_1, \; \; \ pi (i_2) = p_2, \; \; ..., \; \; \ pi (i_k) = p_k.{ 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$

Например, если $n=5$ то перестановка $12453$ избегает $134$ как подпоследовательность, а перестановка $\mathbf{1}2\mathbf{3}5\mathbf{4}$ - нет.

Вопрос: Пусть $k$ постоянная. Принимая во внимание множество $S\subset C(n,k)$ из $k$ -кортежей, найти перестановки $\pi:[n]\rightarrow [n]$ , что позволяет избежать каждого $k$ -кратного в $S$ .

1. Существует ли алгоритм для этой задачи, полиномиальный по $|P|$а $n$ ? Здесь $n$ дано в одинарном. Алгоритм, работающий во времени $n^{f(k)}|P|^{g(k)}$ , будет в порядке.
2. Или эта проблема NP-полная?

Любые ссылки на эту проблему или предложения алгоритмов приветствуются. Обратите внимание, что понятие избегания перестановки, определенное выше, не совпадает с понятием избегания перестановки, где важен только относительный порядок элементов, и которое, кажется, хорошо изучено в комбинаторике.

Он NP-завершен для уменьшением от промежуточности . В проблеме промежуточности каждому дается элементов, которые должны быть полностью упорядочены, и ограничения на некоторые тройки элементов вынуждают один элемент тройки находиться между двумя другими. В вашей задаче одно и то же ограничение можно навязать, запретив все подпоследовательности для трех элементов, которые не помещают средний элемент в середину. Но между ними, как известно, NP-полнота: см. J. Opatrny, Задача полного упорядочения, SIAM J. Comput. 8 (1979), с. 111–114.$k=3$$n$