FPT Parameterisations of Fractional and Generalised Hypertree Width
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-17
DOI: 10.1145/3801900 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Matthias Lanzinger und 2 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Gefördert von: Vienna Science and Technology Fund.
Abstract (Originalsprache)
We present the first fixed-parameter tractable (FPT) algorithms for exact computation of generalized hypertree width (ghw) and fractional hypertree width (fhw). Our algorithms are parameterized by the target width, the rank, and the maximum degree of the input hypergraph. More generally, we show that testing f -width is in FPT for a broad class of width functions that we call manageable. This class contains the edge cover number ρ and its fractional relaxation ρ * , and thus covers both generalized and fractional hypertree width. We additionally extend our framework to also obtain an fpt algorithm for computing a discretized version of adaptive width. Our approach extends a recent algorithm for treewidth (Bojańcyk #38; Pilipczuk, LMCS 2022) that utilises monadic second-order transductions. To extend this idea beyond treewidth we develop new combinatorial machinery around elimination forests in hypergraphs, culminating in a structural normal form for optimal witnesses that makes transduction-based optimisation applicable in the much more general context of manageable width functions. This yields the first exact FPT algorithms for these measures under any nontrivial parameterisation and provides structural tools that may enable more direct optimisation algorithms.
Förderung
- Vienna Science and Technology Fund
Zitieren
APA
Lanzinger, M., Razgon, I., & Unterberger, D. (2026). FPT Parameterisations of Fractional and Generalised Hypertree Width. Proceedings of the ACM on Management of Data, 4(2), 1-17. https://doi.org/10.1145/3801900
Vancouver
Lanzinger M, Razgon I, Unterberger D. FPT Parameterisations of Fractional and Generalised Hypertree Width. Proceedings of the ACM on Management of Data. 2026;4(2):1-17. doi:10.1145/3801900
BibTeX
@article{Lanzinger2026,
author = {Lanzinger, Matthias and Razgon, Igor and Unterberger, Daniel},
title = {FPT Parameterisations of Fractional and Generalised Hypertree Width},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--17},
doi = {10.1145/3801900}
}
EUVIMED