Embedding ordered sets into distributive lattices (Q2520717)

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.