Dömötör Pálvölgyi - Weak embeddings of posets to the Boolean lattice

dmtcs:3684 - Discrete Mathematics & Theoretical Computer Science, January 24, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-7
Weak embeddings of posets to the Boolean latticeArticle

Authors: Dömötör Pálvölgyi ORCID

    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 to the two middle levels of some hypercube.

    https://doi.org/10.23638/DMTCS-20-1-7
    Source: arXiv.org:1606.08226
    Volume: Vol. 20 no. 1
    Section: Graph Theory
    Published on: January 24, 2018
    Accepted on: January 13, 2018
    Submitted on: May 24, 2017
    Keywords: Computer Science - Discrete Mathematics, Mathematics - Combinatorics
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • Cover-decomposition of multiple coverings under conditions involving randomness; Funder: European Commission; Code: 660400

    Share and export

    Consultation statistics

    This page has been seen 928 times.
    This article's PDF has been downloaded 730 times.