Fractional covers of Hypergraphs with bounded multi-intersection
- Submitting institution
-
Birkbeck College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1117
- Type
- E - Conference contribution
- DOI
-
10.4230/LIPIcs.MFCS.2020.41
- Title of conference / published proceedings
- 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
- First page
- 1
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- August
- Year of publication
- 2020
- URL
-
https://drops.dagstuhl.de/opus/volltexte/2020/12731/
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
1 - Algorithms, Verification and Software
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- We design the first efficient algorithm for computing fractional hypertree width for hypergraphs of bounded multiple intersection (BMI). This is the most general class of graphs for which the fractional hypertree width is known to be efficiently computable and hence the result is a significant contribution to hypertreewidth research. At the heart of the method lies a deep combinatorial result stating that a small fractional edge cover of a BMI hypergraph can be realized with non-zero assignment to a small number of hyperedges. Previously such a result was known only for a very restricted subset of BMI hypergraphs.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -