Paper accepted at the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
The International Symposium on Parameterized and Exact Computation (IPEC) is the leading conference for parameterized and exact algorithmics. It thus covers two of the most promising approaches to tackle NP-hard problems. The symposium embraces both new techniques regarding the design of algorithms as well as complexity theoretic results in the field. IPEC is part of the ALGO meeting and will be held this year in Aarhus, Denmark, from August 24 to 26.
The Algorithm Engineering group contributes the following paper which is the result of a close cooperation with the Information Systems group at HPI lead by Prof. Felix Naumann:
The Parameterized Complexity of Dependency Detection in Relational Databases
by Thomas Bläsius, Tobias Friedrich, and Martin Schirneck.
Abstract: We study the parameterized computational complexity of classical problems that arise in the profiling of relational data. Namely, we characterize the complexity of detecting unique column combinations (candidate keys), functional dependencies and inclusion dependencies with the solution size as parameter. While the discovery of uniques and functional dependencies, respectively, turns out to be W-complete, the detection of inclusion dependencies is one of the first natural problems proven to be complete for the class W. As a side effect, our reductions give insights on the complexity of enumerating all inclusion-wise minimal unique column combinations or functional dependencies.