The Complexity of the Partial Order Dimension Problem

1982/09/01 by Mihalis Yannakakis · 4 citations
Computer Science · Engineering · Mathematics · #Graph Labeling and Dimension Problems #graph theory and CDMA systems #Advanced Graph Theory Research #Mathematics #Dimension (graph theory) #Intersection (aeronautics) #Order (exchange) #Combinatorics #Complex dimension #Pure mathematics

paper · doi:10.1137/0603036

openalex publication_date 1982/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/30

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 1 or 2. We prove that it is NP-complete to determine if a partial order has dimension 3. As a consequence, several other related dimension-type problems are shown to be NP-complete.

Citations

• Some simplified NP-complete graph problems
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Partially Ordered Sets
• Algorithmic Graph Theory and Perfect Graphs

Cited by

• Large Induced Subgraphs via Triangulations and CMSO
• Determining Factorial Speed Fast
• Comparability graphs and intersection graphs
• Order dimension [wikipedia]