Total Ordering ProblemTotal Ordering ProblemOpatrny, Jaroslav1979

Paper summaryacawikiProves the NP-completeness of the total ordering problem: given finite sets $S$ and $R$, where $R$ is a subset of $S \times S \times 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 \cite{garey1979computers}.

Proves the NP-completeness of the total ordering problem: given finite sets $S$ and $R$, where $R$ is a subset of $S \times S \times 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 \cite{garey1979computers}.

Your comment:

You must log in before you can post this comment!

You must log in before you can submit this summary! Your draft will not be saved!

Preview:

0

Short Science allows researchers to publish paper summaries that are voted on and ranked! About