Design, Analysis, and Engineering of Enumeration Algorithms

• Applicant: Dr. Martin Schirneck
• Subject Area: Theoretical Computer Science
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 556899211

Many computational tasks in data mining, bioinformatics, or artificial intelligence do not have a notion of a single-best solution. Instead, they require a diverse set of options and in some cases the enumeration of all possible solutions. Progress in enumeration is currently impeded by a divide between theory and practice. Present-day methods often face bottlenecks that have already been addressed in the algorithms community, but are not yet resolved in practice. Conversely, the theoretical research of input structures allowing for improved enumeration does not necessarily align with the instances seen in applications. We aim at mending this divide specifically for the Transversal Hypergraph problem of generating all inclusion-wise minimal hitting sets of a hypergraph. This requires research in three main areas. First, we investigate the combinatorics of real-world hypergraphs. They often exhibit a heterogeneous degree distribution and small hitting sets. Secondly, we apply methods from algorithm engineering to quantify the impact that heuristics and data structures have in speeding up practical algorithms. Finally, we tackle the engineering challenges that hold back the transfer of theoretical insights to practical applications. Here, the profiling of relational databases is an area where our results can have an immediate impact.

• DFG Programme: Research Grants