Paper Info
Title
Weak embeddings of posets to the Boolean lattice.
Abstract
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 Patkos. 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.
Year
Venue
Keywords
2018
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
extremal combinatories,forbidden subposet,NP-completeness
DocType
Volume
Issue
Journal
20.0
1.0
ISSN
Citations 
PageRank 
1462-7264
0
0.34
References 
Authors
6
1
Name
Order
Citations
PageRank
Dömötör Pálvölgyi120229.14