2015/01/06 by Felsner, Stefan, Mustata, Irina, Pergel, Martin · 1 citation
#05C62 #06A07 #68Q25 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1501.01147
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 showed that for k≥ 3 to test if a partial order has dimension ≤ 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≥ 4 to test if a partial order of height 2 has dimension ≤ 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.