Sie sind hier

Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling

Martin Schirneck (Hasso-Plattner-Institut)

Solving an enumeration problem means producing all possible answers to some combinatorial question. This is very different from computing a single number as the output of an optimization problem, let alone a single bit for a decision problem. Not surprisingly, the challenges that come up in the design and analysis of enumeration algorithms are others than those that we usually encounter in algorithm engineering and theoretical computer science.

In this talk, I present an enumeration algorithm for minimal hitting sets of hypergraphs and apply it to the task of detecting unique column combinations in relational databases.
While I touch on some of the challenges specific to enumeration, I mainly want to show how the enumeration perspective can inspire new insights also for other fields of computer science, for example, parameterized complexity theory. In particular, I prove that the extension problem for minimal hitting sets, a subproblem in our algorithm, is complete for the parameterized class W[3]. It is one of the first known natural problems to have this property.

This is joint work with Thomas Bläsius, Tobias Friedrich, Julius Lischeid, and Kitty Meeks.


Date
Speaker
Location
Language
23.01.2020
16:15
Martin Schirneck
TEL 512
English

Back to the research colloquium site.

To top