Given once, 2015

Unique Covering Problems with Geometric Sets

Covering points with lines, squares, or hyperplanes so that many are covered exactly once

Parameterized algorithms · Kernelization · Computational geometry

An advanced research talk, for graduate students and up.

Abstract

Draft, not yet checked by me

Set 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.

Where I have given it

All appearances