<p>It's NP-complete for $k=3$ by a reduction from <a href="https://en.wikipedia.org/wiki/Betweenness">betweenness</a>. 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, <em>SIAM J. Comput.</em>, 8 (1979), pp. 111–114.</p>

CC BY-SA 4.0
2024-01-21T17:49:33.563Z
What about k=2?
Felix Goldberg
CC BY-SA 3.0
2015-08-19T16:17:30.697Z
2015-08-20T01:05:48.563Z
2015-08-20T01:05:48.563Z
David Eppstein
<p>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&lt;i_2&lt;...&lt;i_k$ such that 
$$\pi(i_1) = p_1, \;\;\pi(i_2)=p_2,\;\;  ...,\;\;\pi(i_k) = p_k.$$</p>

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

<p><strong>Question:</strong> 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$.  </p>

<ol>
<li>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.</li>
<li>Or is this problem NP-complete? </li>
</ol>

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

CC BY-SA 3.0
2015-08-19T19:51:47.590Z
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?
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-08-19T19:53:16.827Z
Sorry, I overlooked that you have a *set* of forbidden tuples.  There's no guarantee that rejection sampling will be efficient.
D.W.
<reference-request><co.combinatorics><permutations>
Permutations with forbidden subsequences
Mateus de Oliveira Oliveira
# Permutations with forbidden subsequences

(Asked by: username_0 on 2015-08-19)

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

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.

**Tags:** reference-request, co.combinatorics, permutations

> **Comments:**
> **username_0**: 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?  
> **username_1**: Sorry, I overlooked that you have a *set* of forbidden tuples.  There's no guarantee that rejection sampling will be efficient.  

---

## 1 answers

### Answer by username_2 on 2015-08-19. Score: 14 | Accepted answer

It's NP-complete for $k=3$ by a reduction from [betweenness](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_3**: What about k=2?  

---

