Permutacje z zabronionymi podsekwencjami

Niech oznacza zbiór a C (n, k) oznacza zbiór wszystkich kombinacji elementów z bez powtórzeń. Niech będzie liczbą w . Mówimy, że permutacja zestawu pozwala uniknąć jeśli nie ma k-krotki liczb całkowitych taki, że { 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$

Na przykład, jeśli to permutacja 12453 unika 134 jako podsekwencji, podczas gdy permutacja \ mathbf {1} 2 \ mathbf {3} 5 \ mathbf {4} nie.12453 134 1 2 3 5 $n=5$$12453$$134$$\mathbf{1}2\mathbf{3}5\mathbf{4}$

Pytanie: Niech $k$ będzie stałą. Biorąc pod uwagę zestaw $S\subset C(n,k)$ od $k$ -tuples, znaleźć permutacji $\pi:[n]\rightarrow [n]$ , która pozwala uniknąć każdej $k$ -tuple w $S$ .

1. Czy istnieje algorytm tego problemu, który jest wielomianowy w $|P|$a $n$ ? Tutaj $n$ jest podany unarnie. Algorytm działający w czasie $n^{f(k)}|P|^{g(k)}$ byłby w porządku.
2. Czy jest to problem NP-zupełny?

Wszelkie odniesienia do tego problemu lub sugestie algorytmów są mile widziane. Zauważ, że zdefiniowane powyżej pojęcie unikania permutacji nie jest takie samo, jak pojęcie unikania permutacji, w którym ważny jest tylko względny porządek elementów i który wydaje się być dobrze zbadany w kombinatoryce.

Jest NP-kompletny dla przez redukcję od międzyczasie . W przypadku problemu pośredniczącego, jeden otrzymuje elementów, które mają być całkowicie uporządkowane, a ograniczenia dotyczące niektórych potrójnych elementów zmuszają jeden element potrójnego do umieszczenia między pozostałymi dwoma. W twoim problemie to samo ograniczenie można wymusić, zakazując wszystkich podsekwencji trzech elementów, które nie umieszczają środkowego elementu na środku. Ale wiadomo, że wzajemność jest NP-zupełna: patrz J. Opatrny, Problem z całkowitym uporządkowaniem, SIAM J. Comput. , 8 (1979), s. 111–114.$k=3$$n$