Hypergraph Parameters: Structure and Algorithmic Application

Most fundamental problems that arise in various areas of computer science and beyond, such as constraint satisfaction, resource allocation, graph drawing, neural network learning, and many others, cannot be solved efficiently: based on common complexity-theoretical assumptions, these problems do not admit algorithms with polynomial running times. Despite their differences, all these problems have a common characteristic: their complexity is derived from an exponential search space, even though the structure of a potential solution is relatively simple. Parameterized complexity provides a powerful set of tools to overcome the intractability of such problems by designing efficient algorithms for specific classes of instances. This process often occurs gradually, when identification of some basic property (parameter) that enables a fast algorithm is followed by sequential relaxations, resulting in as general restrictions as possible. Many problems admit a natural graph representation, which has led to the development of a rich hierarchy of structural graph parameters. Numerous works have been conducted in parameterized complexity, exploring the limits of tractability with respect to these parameters. Graphs are convenient for expressing problems that deal with elements of a set (which become vertices) and binary functions or relations on this set (encoded as edges, possibly weighted). Compared to them, hypergraphs offer additional expressive power, allowing one to represent functions and relations of arbitrary complexity by encoding these as hyperedges. Although there have been efforts to develop hypergraph analogues of well- established graph parameters, the toolbox for dealing with hypergraphs is still much more limited than that for graphs. The goal of this project is to deepen the understanding of existing hypergraph parameters and to discover new ones to address the gaps in parameterized complexity of hypergraph problems.