EUVIMEDEUVIMED entdecken
Crossref

FPT Parameterisations of Fractional and Generalised Hypertree Width

Matthias Lanzinger, Igor Razgon, Daniel Unterberger

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →