Permutations with forbidden subsequences

Question

Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition. Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a permutation $\pi:[n]\rightarrow [n]$ of the set $[n]$ avoids $p$ if there is no k-tuple of integers $i_1<i_2<...<i_k$ such that $$\pi(i_1) = p_1, \;\;\pi(i_2)=p_2,\;\; ...,\;\;\pi(i_k) = p_k.$$

For instance, if $n=5$ then the permutation $12453$ avoids $134$ as a subsequence, while the permutation $\mathbf{1}2\mathbf{3}5\mathbf{4}$ does not.

Question: Let $k$ be a constant. Given a set $S\subset C(n,k)$ of $k$-tuples, find a permutation $\pi:[n]\rightarrow [n]$ that avoids each $k$-tuple in $S$.

1. Is there an algorithm for this problem that is polynomial in $|P|$ and $n$? Here $n$ is given in unary. An algorithm running in time $n^{f(k)}|P|^{g(k)}$ would be fine.
2. Or is this problem NP-complete?

Any references for this problem, or suggestions of algorithms are welcome. Note that the notion of permutation avoiding subsequence defined above is not the same as the notion of permutation avoiding pattern where only the relative order of elements is important, and which seems to be well studied in combinatorics.

Answer 1

It's NP-complete for $k=3$ by a reduction from betweenness. In the betweenness problem, one is given $n$ items to be totally ordered, and constraints on some triples of items forcing one item of the triple to be between the other two. In your problem, the same constraint can be forced by forbidding all the subsequences on three elements that do not place the middle element in the middle. But betweenness is known to be NP-complete: see J. Opatrny, Total ordering problem, SIAM J. Comput., 8 (1979), pp. 111–114.