The Complexity of the Partial Order Dimension Problem: Closing the Gap

DOI10.1137/15M1007720zbMATH Open1360.06001arXiv1501.01147OpenAlexW2963499318MaRDI QIDQ2957691

Author name not available (Why is that?)

Publication date: 27 January 2017

Published in: (Search for Journal in Brave)

Abstract: 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 $kgeq3$ to test if a partial order has dimension $leqk$ is NP-complete. The height of a partial order $P$ is the maximum size of a chain in $P$. Yannakakis also showed that for $kgeq4$ to test if a partial order of height $2$ has dimension $leqk$ 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.

Full work available at URL: https://arxiv.org/abs/1501.01147

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: The Complexity of the Partial Order Dimension Problem: Closing the Gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957691)