The complexity of the partial order dimension problem: closing the gap

DOI10.1137/15M1007720MaRDI QIDQ2957691zbMATH OpenOpenAlexFDO

Authors Stefan Felsner, Irina Mustaţă, Martin Pergel

Publication date 27 January 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

intersection graphNP-completenesstriangle containment

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• The Hardness of Approximating Poset Dimension
• On recognizing the dimension of a poset
• scientific article; zbMATH DE number 512933
• A Poset Dimension Algorithm
• On the complexity of partial order properties

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• Computing the dimension of N-free ordered sets is NP-complete
• Fractional dimension of partial orders
• Geodesic embeddings and planar graphs
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 736305 (Why is no real title available?)
• scientific article; zbMATH DE number 1161251 (Why is no real title available?)
• scientific article; zbMATH DE number 1554930 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• Intersection graphs of segments
• On the fractional dimension of partially ordered sets
• On the order dimension of outerplanar maps
• Partially Ordered Sets
• Permutation Graphs and Transitive Graphs
• Planar Formulae and Their Uses
• Planar graphs and poset dimension
• Planar graphs as minimal resolutions of trivariate monomial ideals
• Polynomial time and parameterized approximation algorithms for boxicity
• Schnyder woods and orthogonal surfaces
• The Complexity of the Partial Order Dimension Problem
• The Hardness of Approximating Poset Dimension
• The Order Dimension of Convex Polytopes

Cited in

(13)

• Edge subdivision and dimension
• On recognizing the dimension of a poset
• On the complexity of diagram testing
• Sublinear approximation algorithms for boxicity and related problems
• Computational aspects of the 2-dimension of partially ordered sets
• The fine-grained complexity of multi-dimensional ordering properties
• A Poset Dimension Algorithm
• scientific article; zbMATH DE number 1554930 (Why is no real title available?)
• The complexity of embedding orders into small products of chains
• The fine-grained complexity of multi-dimensional ordering properties
• On unit grid intersection graphs and several other intersection graph classes
• Graph theory. Abstracts from the workshop held January 5--10, 2025
• Grid intersection graphs and order dimension

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)