Weak embeddings of posets to the boolean lattice
Megjelenés dátuma: 2018
MTMT: 3357432
WoS ID: 000489685900005
Scopus ID: 85044434938
Absztrakt:
The goal of this paper is to prove that several variants of deciding whether a poset can be (weakly) embedded into a small Boolean lattice, or to a few consecutive levels of a Boolean lattice, are NP-complete, answering a question of Griggs and of Patkós. As an equivalent reformulation of one of these problems, we also derive that it is NP-complete to decide whether a given graph can be embedded into the two middle levels of some hypercube. © 2018 by the author(s)