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 View the MathML source. 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 View the MathML source time, and thus outperforms the View the MathML source 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.