Fractional covers of hypergraphs with bounded multi-intersection
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 pre...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2023
|
| _version_ | 1826311391421661184 |
|---|---|
| author | Gottlob, G Lanzinger, MP Pichler, R Razgon, I |
| author_facet | Gottlob, G Lanzinger, MP Pichler, R Razgon, I |
| author_sort | Gottlob, G |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T08:07:42Z |
| format | Journal article |
| id | oxford-uuid:26e64e3a-0eec-48cd-b33a-bba7b743f52f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:07:42Z |
| publishDate | 2023 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:26e64e3a-0eec-48cd-b33a-bba7b743f52f2023-11-14T11:27:24ZFractional covers of hypergraphs with bounded multi-intersectionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:26e64e3a-0eec-48cd-b33a-bba7b743f52fEnglishSymplectic ElementsElsevier2023Gottlob, GLanzinger, MPPichler, RRazgon, IFractional (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. |
| spellingShingle | Gottlob, G Lanzinger, MP Pichler, R Razgon, I Fractional covers of hypergraphs with bounded multi-intersection |
| title | Fractional covers of hypergraphs with bounded multi-intersection |
| title_full | Fractional covers of hypergraphs with bounded multi-intersection |
| title_fullStr | Fractional covers of hypergraphs with bounded multi-intersection |
| title_full_unstemmed | Fractional covers of hypergraphs with bounded multi-intersection |
| title_short | Fractional covers of hypergraphs with bounded multi-intersection |
| title_sort | fractional covers of hypergraphs with bounded multi intersection |
| work_keys_str_mv | AT gottlobg fractionalcoversofhypergraphswithboundedmultiintersection AT lanzingermp fractionalcoversofhypergraphswithboundedmultiintersection AT pichlerr fractionalcoversofhypergraphswithboundedmultiintersection AT razgoni fractionalcoversofhypergraphswithboundedmultiintersection |