Total ordering problem

Citation: J. Opatrný (1979) Total ordering problem. SIAM Journal on Computing (RSS)
DOI (original publisher): 10.1137/0208008
Semantic Scholar (metadata): 10.1137/0208008
Sci-Hub (fulltext): 10.1137/0208008
Internet Archive Scholar (search for fulltext): Total ordering problem
Tagged: Computer Science (RSS) complexity (RSS), np-complete (RSS), computational complexity (RSS)

Summary

Proves the NP-completeness of the total ordering problem: given finite sets S and R, where R is a subset of S x S x S, does there exist a total ordering of the elements of S such that for all (x, y, z) in R, either x < y < z or z < y < x? The reduction is from the hypergraph 2-colorability problem with edges of size at most 3.

This problem is in "Computers and Intractibility" by Garey and Johnson as problem MS1, the betweenness problem.

References

Garey, M. R.; Johnson, D. S. (1979), Computers and Intractibility: a guide to the theory of NP-completeness, W.H. Freeman