2
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Isn't it this paper on research gate researchgate.net/publication/… ? $\endgroup$
    – Louis
    Jan 8 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$
    – steven kelk
    Jan 8 at 12:23

0

Reset to default

Your Answer

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