Next week (March 13 and 14) Kitty Meeks will visit the Algorithm Engineering group at HPI. Ms. Meeks is a Personal Research Fellow of the Royal Society of Edinburgh, affiliated with the University of Glasgow. She is working primarily in the field of computational complexity and will give a talk in the group's research seminar on Monday, March 13 at 1.30 pm.
Title: The complexity of finding and counting sum-free subsets.
Abstract: A set A of natural numbers is said to be sum-free if it does not contain x, y and z such that x + y = z. Sum-free sets have been studied extensively in additive combinatorics (Paul Erdős was particularly interested in these sets) but algorithmic questions relating to sum-free sets have thus far received very little attention. We consider the problem, given a set A, of determining whether A contains a sum-free subset of size at least k. We show that this problem is NP-complete in general, but is tractable with respect to certain parameterizations; in the cases where the decision problem is tractable, we also consider the complexity of counting all sum-free subsets of size exactly k.
This is joint work with Andrew Treglown (University of Birmingham).
