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 ⋃h i=1 iX. 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 i