TY - JOUR
TI - Complexity of Cover-Preserving Embeddings of Bipartite Orders Into Boolean Lattices
AU - Herman, Grzegorz
TI - Complexity of Cover-Preserving Embeddings of Bipartite Orders Into Boolean Lattices
AB - We study the problem of deciding, whether a given partial order is embeddable into two consecutive layers of a Boolean lattice. Employing an equivalent condition for such em- beddability similar to the one given by J. Mittas and K. Reuter [5], we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisfiability problem.
VL - 2014
IS - Number 49
PY - 2014
SN - 0137-2904
C1 - 2084-2589
SP - 99
EP - 117
DO - 10.4467/20842589RM.14.006.2276
UR - https://ejournals.eu/en/journal/reports-on-mathematical-logic/article/complexity-of-cover-preserving-embeddings-of-bipartite-orders-into-boolean-lattices