Embedding ordered sets into distributive lattices
type: Item
instance of: scholarly article
title: Embedding ordered sets into distributive lattices
zbMATH Open document ID: 1357.06002
author: C. J. van Alten
published in: Order
publication date: 2016-12-16T00:00:00Z
review text: In this paper, the author investigates the decision problem: DistPO: Given a finite ordered set, is it embeddable into a distributive lattice with preservation of existing meets and joins? The main result of the paper is that DistPO is NP-complete. The NP-hardness is achieved by a polynomial reduction to the 3SAT decision problem to DistPO and membership in NP is proved by presenting a suitable NP-algorithm. The author also shows that the results above extend to the bounded case, i.e., to the decision problem: BoundedDistPO: Given a finite bounded ordered set, is it embeddable into a bounded distributive lattice with preservation of existing meets and joins? The requirement that all existing finite meets and joins are preserved could be weakened so that only joins of sets up to size \(k\) and meets of sets up to size \(p\) are preserved where \(k, l\geq 2\). The author shows that NP-completeness holds in the case \(k\geq 3\) and \(l\geq 2\). The case \(k=l=2\) is left open.
Mathematics Subject Classification ID: 06D05
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6664958
zbMATH Keywords: ordered set
zbMATH Keywords: distributive lattice
zbMATH Keywords: NP-completeness
reviewed by: Hernando Gaitán
MaRDI profile type: Publication
full work available at URL: s11083-015-9376-6
OpenAlex ID: W2246642039
cites work: Q3116854
cites work: Q4530231
cites work: Canonical extensions of posets.
cites work: Q4525257
cites work: Lattices and bases of Coxeter groups
cites work: Partially Ordered Sets
cites work: The complexity of embedding orders into small products of chains
cites work: Order dimension, strong Bruhat order and lattice properties for posets
cites work: Q3392275
cites work: Q4004146
cites work: The Complexity of the Partial Order Dimension Problem
DOI: 10.1007/S11083-015-9376-6
description: scientific article