Some algorithmic results for [2]-sumset covers

Let X={xi:1≤i≤n}⊂N+, and h∈N+. The h-iterated sumset of X, denoted hX, is the set {x1+x2+…+xh:x1,x2,…,xh∈X}, and the [h]-sumset of X, denoted [h]X, is the set ⋃i=1hiX. A [h]-sumset cover of S⊂N+ is a set X⊂N+ such that S⊆[h]X. In this paper, we focus on the case h=2, and study the APX-hard problem of computing a minimum cardinality [2]-sumset cover X of S (i.e. computing a minimum cardinality set X⊂N+ such that every element of S is either an element of X, or the sum of two - non-necessarily distinct - elements of X). We propose two new algorithmic results. First, we give a fixed-parameter tractable (FPT) algorithm that decides the existence of a [2]-sumset cover of size at most k of a given set S. Our algorithm runs in O(2(3log⁡k−1.4)kpoly(k)) time, and thus outperforms the O(5k2(k+3)2k2log⁡(k)) time FPT result presented in Fagnot et al. (2009) [5]. Second, we show that deciding whether a set S has a smaller [2]-sumset cover than itself is NP-hard.