Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

06.03.2017

Scientific Guest from the University of Glasgow

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