文章基本信息

标题：Fractional Covers of Hypergraphs with Bounded Multi-Intersection
本地全文：下载
作者：Georg Gottlob ; Matthias Lanzinger ; Reinhard Pichler 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：41:1-41:14
DOI：10.4230/LIPIcs.MFCS.2020.41
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. This allows us to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is â¤ k for some constant k. We also show how our results translate to fractional vertex covers.
关键词：Fractional graph theory; fractional edge cover; fractional hypertree width; bounded multi-intersection; fractional cover; fractional vertex cover