15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean taking a permutation at random and verifying whether it doesn't violate any constraints in S? A randomized polynomial time algorithm would be better than nothing. k is assumed to be a constant, so it is by definition small. But I don't see how it would work efficiently if S has many constraints. Since by David's answer, the problem is NPC for k=3, I'm a bit skeptical that a randomized algorithm would be efficient. Could you please explain a little bit your idea? $\endgroup$ – Mateus de Oliveira Oliveira Aug 19 '15 at 19:51
  • $\begingroup$ Sorry, I overlooked that you have a set of forbidden tuples. There's no guarantee that rejection sampling will be efficient. $\endgroup$ – D.W. Aug 19 '15 at 19:53
13
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.