Complexity Analysis of Generalized and Fractional Hypertree Decompositions

DOI10.1145/3457374zbMath1499.68272arXiv2002.05239OpenAlexW3200757673MaRDI QIDQ5056426

Reinhard Pichler, Matthias Lanzinger, Georg Gottlob, Igor Razgon

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.05239

zbMATH Keywords

hypergraphsNP-hardnesstractable fragmentscandidate tree decompositionsfractional hypertree decompositionsgeneralized hypertree decompositionsmulti-intersection width

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Fractional covers of hypergraphs with bounded multi-intersection

This page was built for publication: Complexity Analysis of Generalized and Fractional Hypertree Decompositions