COMPLEXITY OF COVER-PRESERVING EMBEDDINGS OF BIPARTITE ORDERS INTO BOOLEAN LATTICES
COMPLEXITY OF COVER-PRESERVING EMBEDDINGS OF BIPARTITE ORDERS INTO BOOLEAN LATTICES

Summary/Abstract: 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 embeddability similar to the one given by J. Mittas and K. Reuter, 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.

• Details
• Contents