We’re excited to announce that Matthias Lanzinger, Igor Razgon, and Daniel Unterberger have won a Distinguished Paper Award at the 2026 ACM SIGMOD/PODS Conference for their paper “FPT Parameterisations of Fractional and Generalised Hypertree Width”!

Many computational problems can be solved more efficiently when the underlying data has a simple structure. Measures such as generalized and fractional hypertree width describe how close a hypergraph—a mathematical model in which relationships can involve more than two objects—is to having a tree-like structure. Although these measures play an important role in areas such as databases, constraint solving, and artificial intelligence, computing them exactly has remained challenging.

FPT Parameterisations of Fractional and Generalised Hypertree Width presents the first fixed-parameter tractable algorithms for computing generalized and fractional hypertree width exactly under a meaningful set of parameters. The authors show that their framework applies to a broad class of related structural complexity measures, including a discretized version of adaptive width. To achieve this, they develop new combinatorial techniques for hypergraphs that extend methods previously available only for ordinary graphs. Beyond providing the first exact algorithms for these important measures, the work introduces a new theoretical framework that may enable more efficient algorithms for analyzing the structure of complex data in the future.

The annual Association for Computing Machinery (ACM) SIGMOD/PODS Conference is one of the leading international venues for the database community, bringing together researchers, practitioners, developers, and users to discuss recent advances in database systems and data management. The conference features a comprehensive technical program, an industry exhibition, and career panels, but also showcases emerging work in the field.

Congratulations to Matthias, Igor Razgon, and Daniel on this outstanding achievement!

Abstract

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 𝑓-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 that utilizes 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 optimization algorithms.

About the authors

Matthias Lanzinger is an Assistant Professor at the Research Unit Databases and Artificial Intelligence at TU Wien Informatics. His research lies at the intersection of logic, algorithms, complexity theory, and machine learning. He studies the computational complexity of reasoning and learning problems, with a particular interest in how structural properties of data and tasks give rise to efficient algorithms. His work combines methods from theoretical computer science and database theory to understand the fundamental limits of data analysis and AI. Before joining TU Wien, Matthias was a Senior Research Associate at the University of Oxford. His research has been published in leading venues in theoretical computer science and artificial intelligence, and he is currently a co-PI of the Vienna Science and Technology Fund (WWTF) funded project Decompose and Conquer: Fast Query Processing via Decomposition (DeConquer) on scalable reasoning in complex data systems.

Daniel Unterberger is a doctoral student at TU Wien Informatics, where they also earned their master’s degree in Mathematics. They are a member of the Research Unit Databases and Artificial Intelligence, and are also part of the WWTF-funded project (DeConquer). Their research interests include algorithms, database theory, complexity theory, and logic, with a particular focus on the limits on efficiency of database systems through the lens of parameterized complexity. Through their work, they investigate fundamental questions in computation, information management, and mathematical reasoning, contributing to a deeper understanding of the principles that underpin modern computing.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.