The Complexity of the Partial Order Dimension Problem: Closing the Gap
Stefan Felsner, Irina Mustaţă, Martin Pergel · SIAM Journal on Discrete Mathematics · 2017
The dimension of a partial order $P$ is the minimum number of linear orders whose intersection is $P$. There are efficient algorithms to test if a partial order has dimension at most 2. In 1982 Yannakakis [SIAM J. Algebraic Discrete Methods, 3 (1982), pp. 351--358] showed that for $k\geq 3$ to test if a partial order has dimension $\leq k$ is NP-complete. The height of a partial order $P$ is the maximum size of a chain in $P$. Yannakakis also showed that for $k\geq 4$ to test if a partial order of height $2$ has dimension $\leq k$ is NP-complete. The complexity of deciding whether an order of height 2 has dimension 3 was left open. This question became one of the best known open problems in dimension theory for partial orders. We show that the problem is NP-complete. Technically, we show that the decision problem (3DH2) for dimension is equivalent to deciding for the existence of bipartite triangle containment representations (BTCon). This problem then allows a reduction from a class of planar satisfiability problems (P-3-CON-3-SAT(4)) which is known to be NP-hard.