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 $[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$

π (i_{1}) = p_{1}, π (i_{2}) = p_{2}, . . ., π (i_{k}) = p_{k} .

$\pi(i_1) = p_1, \;\;\pi(i_2)=p_2,\;\; ...,\;\;\pi(i_k) = p_k.$

Na przykład, jeśli to permutacja unika jako podsekwencji, podczas gdy permutacja nie. $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$ .

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.
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.

reference-request co.combinatorics permutations

— Mateus de Oliveira Oliveira
źródło

Czy masz na myśli losową permutację i sprawdzenie, czy nie narusza ona żadnych ograniczeń w S? Randomizowany algorytm wielomianu czasu byłby lepszy niż nic. przyjmuje się, że k jest stałą, więc z definicji jest małe. Ale nie rozumiem, jak działałoby to efektywnie, gdyby S miał wiele ograniczeń. Ponieważ w odpowiedzi Davida problemem jest NPC dla k = 3, jestem nieco sceptyczny, że losowy algorytm byłby skuteczny. Czy mógłbyś wyjaśnić trochę swój pomysł?

— Mateus de Oliveira Oliveira,

Przepraszam, przeoczyłem, że masz zestaw zabronionych krotek. Nie ma gwarancji, że próbkowanie przy odrzuceniu będzie skuteczne.

— DW,

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$

— David Eppstein
źródło