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.
Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Parameterized Complexity of Dependency Detection in Relational Databases. International Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1--6:13
We study the parameterized 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 into the complexity of enumerating all minimal unique column combinations or functional dependencies.
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.