COMPLEXITY OF COVER-PRESERVING EMBEDDINGS OF BIPARTITE ORDERS INTO BOOLEAN LATTICES
Languages of publication
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 , we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisability problem.
07 - 07 - 2015
Publication order reference