Skip to main content

Research Repository

Advanced Search

Fractional covers of hypergraphs with bounded multi-intersection

Gottlob, Georg; Lanzinger, Matthias; Pichler, Reinhard; Razgon, Igor

Authors

Georg Gottlob

Matthias Lanzinger

Reinhard Pichler



Abstract

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. We show how this combinatorial result can be used to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤k for some constant k. Moreover, we show a dual version of our main result for fractional hitting sets.

Citation

Gottlob, G., Lanzinger, M., Pichler, R., & Razgon, I. (2023). Fractional covers of hypergraphs with bounded multi-intersection. Theoretical Computer Science, 979, Article 114204. https://doi.org/10.1016/j.tcs.2023.114204

Journal Article Type Article
Acceptance Date Sep 15, 2023
Online Publication Date Sep 21, 2023
Publication Date Nov 10, 2023
Deposit Date Sep 27, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 979
Article Number 114204
DOI https://doi.org/10.1016/j.tcs.2023.114204
Public URL https://durham-repository.worktribe.com/output/2880035