<p>Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization problem: partition P into a minimum number of monotone subsequences. Crucially, the subsequences are allowed to be a mixture of increasing and decreasing.</p>
<p>The problem is often cited as being NP-hard. As far as I can tell, the proof of this leads back to the following article, typically cited in two different forms:</p>
<ul>
<li><p>K. W. Wagner. Monotonic coverings of finite sets. J. Inf. Process.
Cybern., 20(12):633–639, 1984.</p>
</li>
<li><p>K. Wagner. Monotonic coverings of finite sets. Elektronische
Informationsverarbeitung und Kybernetik 20.12 (1984): 633-639.</p>
</li>
</ul>
<p>See also <a href="https://dblp.org/db/journals/eik/eik20.html" rel="nofollow noreferrer">https://dblp.org/db/journals/eik/eik20.html</a>.</p>
<p>The Journal seems to have undergone several name changes, and if I understand correctly later became the Journal of Automata, Languages and Combinatorics. However, wherever I look, I can't find the article. I have consulted multiple colleagues and they have also drawn a blank.</p>
<p>This leads to my question. <strong>Does anybody have access to this paper and/or can explain what the hardness proof looks like? I would also be happy to see an independent hardness proof.</strong></p>
<p>Thank you in advance!</p>

CC BY-SA 4.0
2023-01-08T11:33:46.903Z
Isn't it this paper on research gate https://www.researchgate.net/publication/220286948_Monotonic_Coverings_of_Finite_Sets ?
Louis
CC BY-SA 4.0
2023-01-08T12:23:24.447Z
Yes it is, thank you! I've really no idea how I missed that... but I'm very glad you have located it. Thanks again.
steven kelk
<cc.complexity-theory><np-hardness><permutations><partition-problem><partial-order>
hardness of partition of permutation into a minimum number of monotone subsequences
steven kelk
# hardness of partition of permutation into a minimum number of monotone subsequences

(Asked by: username_0 on 2023-01-08)

Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization problem: partition P into a minimum number of monotone subsequences. Crucially, the subsequences are allowed to be a mixture of increasing and decreasing.

The problem is often cited as being NP-hard. As far as I can tell, the proof of this leads back to the following article, typically cited in two different forms:

* K. W. Wagner. Monotonic coverings of finite sets. J. Inf. Process.
  Cybern., 20(12):633–639, 1984.
* K. Wagner. Monotonic coverings of finite sets. Elektronische
  Informationsverarbeitung und Kybernetik 20.12 (1984): 633-639.

See also <https://dblp.org/db/journals/eik/eik20.html>.

The Journal seems to have undergone several name changes, and if I understand correctly later became the Journal of Automata, Languages and Combinatorics. However, wherever I look, I can't find the article. I have consulted multiple colleagues and they have also drawn a blank.

This leads to my question. **Does anybody have access to this paper and/or can explain what the hardness proof looks like? I would also be happy to see an independent hardness proof.**

Thank you in advance!

**Tags:** cc.complexity-theory, np-hardness, permutations, partition-problem, partial-order

> **Comments:**
> **username_1**: Isn't it this paper on research gate https://www.researchgate.net/publication/220286948_Monotonic_Coverings_of_Finite_Sets ?  
> **username_0**: Yes it is, thank you! I've really no idea how I missed that... but I'm very glad you have located it. Thanks again.  

---

## 0 answers

