2026-08-07T08:41:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12731 2024-03-06T10:50:38Z ddc:004 open_access

Fractional Covers of Hypergraphs with Bounded Multi-Intersection Gottlob, Georg Lanzinger, Matthias Pichler, Reinhard Razgon, Igor Fractional graph theory fractional edge cover fractional hypertree width bounded multi-intersection fractional cover fractional vertex cover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Georg Gottlob and Matthias Lanzinger and Reinhard Pichler and Igor Razgon 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.41 urn:nbn:de:0030-drops-127317 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.41 eng https://creativecommons.org/licenses/by/3.0/legalcode