Georg Gottlob
Fractional covers of hypergraphs with bounded multi-intersection
Gottlob, Georg; Lanzinger, Matthias; Pichler, Reinhard; Razgon, Igor
Authors
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 |
You might also like
The Treewidth and Pathwidth of Graph Unions
(2024)
Journal Article
Tree-width dichotomy
(2022)
Journal Article
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
(2021)
Journal Article
The splitting power of branching programs of bounded repetition and CNFs of bounded width
(2024)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search