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!

  • 3
    $\begingroup$ Isn't it this paper on research gate researchgate.net/publication/… ? $\endgroup$
    – Louis
    Commented Jan 8, 2023 at 11:33
  • $\begingroup$ 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. $\endgroup$ Commented Jan 8, 2023 at 12:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.