Martin Schirneck

I am the PI of a research project on the Design, Analysis, and Engineering of Enumeration Algorithms funded by the German Research Foundation (“DFG Eigene Stelle”). Enumeration is the task of computing and listing all solutions to a combinatorial problem. The most important problem in enumeration is the generation of the minimal hitting sets of a hypergraph, known as the transversal hypergraph. In this project, I explore the combinatorics of finite sets to find new classes for which the transversal hypergraph problem is tractable. The resulting enumeration algorithms have applications in artificial intelligence and data profiling.

Previously, I was a postdoctoral researcher at the University of Vienna, after obtaining my PhD from the Hasso Plattner Institute in Potsdam.

A short CV can be found here.

My research interests include various topics in mathematics and theoretical computer science. I have contributed to the following areas.

• enumeration algorithms and complexity
• data profiling
• fault-tolerant data structures
• parameterized and fine-grained complexity
• evolutionary computation and randomized search heuristics
• time series classification
• algorithmic learning theory

I collect here some combinatorial questions to which I don't know the answer. If you want to work on them or if you already have a solution, I am happy to hear from you.

For the Transversal Rank problem, you are given a hypergraph $\mathcal{H}$ and a non-negative integer $k$ and you need to decide whether $\mathcal{H}$ has an inclusionwise-minimal hitting set of size at least $k$. (Allowing hitting sets with more than $k$ vertices is what makes this problem hard.) Bazgan et al. proved that the problem is W[1]-hard when parameterized by $k$. Conversely, the following result by Berge and Duchet (1975) shows that the problem is in W[3].

The hypergraph $\mathcal{H}$ has a minimal hitting set of size at least $k$ if and only if there exists $k$ distinct hyperedges $E_1, \dots, E_k \in \mathcal{H}$ such that every hyperedge $E \in \mathcal{H}$ has a vertex $x \in E$ such that $x$ is contained in at most one of the $E_i$.

What is the parameterized complexity of the Transversal Rank problem?

I have been fortunate to work with several outstanding students.

• Simon Wietheger, Winter 2022/23 (HPI): Fair Correlation Clustering in Forests, appeared at FORC 2023
• Benjamin Feldmann, Winter 2019/20 (HPI): Distributed Unique Column Combinations Discovery
• Philipp Fischbeck, Winter 2017/18 (HPI): On the Effectiveness of Data Reduction for Covering Problems in Real-World Transit Networks, appeared at WAW 2019

• Bennet Hörmann, Winter 2025/26: A Lower Bound for Minimal-to-Maximal Conversion Search
• Marc Dollmann, Winter 2022/23 (U Vienna): Graph Clustering: A Comparison of Louvain and Leiden
• Linus Heinzl, Summer 2019 (HPI): Analysis of the Parameter Configuration of the Ramer-Douglas-Peucker Algorithm for Time Series Compression
• Felix Mujkanovic, Summer 2019 (HPI): Explaining the Predictions of Any Time Series Classifier
• Julius Lischeid, Summer 2018 (HPI): Lexicographic Enumeration of Hitting Sets in Hypergraphs, appeared at ALENEX 2019 and JCSS 2022

• Muhammad Raza Ali, Winter 2024/25 (U Vienna): Parallelizing Hitting Set Enumeration Algorithms for Data Profiling
• Winter 2021/22 (HPI): Theory of Crossover-Based Optimization, received a Best Paper Award at GECCO 2022 and appeared at TELO 2023
• Summer 2021 (HPI): Fault Tolerant Algorithms, appeared at ITCS 2022
• Academic Year 2018/19 (HPI): Lossy Compression of Time Series Data
• Winter 2016/17 (HPI): Distributed Evolutionary Search, appeared at GECCO 2017 and Algorithmica 2019

Some of my conference talks are available online.

• AAAI 2025: Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks (slides)
• STOC 2023: Approximate Distance Sensitivity Oracles in Subquadratic Space (slides)
• ITCS 2022: Fixed-Parameter Sensitivity Oracles (slides)
• ESA 2021: Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles (slides)
• ESA 2020: The Minimization of Random Hypergraphs (slides)