Given once, 2015
Unique Covering Problems with Geometric Sets
Covering points with lines, squares, or hyperplanes so that many are covered exactly once
An advanced research talk, for graduate students and up.
Abstract
Draft, not yet checked by meSet Cover asks for a small collection of sets that covers a universe. Two stricter relatives care about uniqueness: Exact Cover wants every element covered exactly once, and Unique Cover wants at least k elements covered exactly once. Both are NP-complete. For abstract set systems, Exact Cover is W[1]-hard, and Unique Cover is FPT but has no polynomial kernel. I make the sets geometric: unit squares or lines covering points in the plane, or hyperplanes in higher dimensions. Here Unique Cover admits polynomial kernels, Exact Cover is FPT for lines and hyperplanes but W[1]-hard for squares, and the new Unique Set Cover problem is FPT for lines and hyperplanes.
The slides
The viewer needs JavaScript; the PDF below works without it.