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!
