Some algorithmic results for [2]-sumset covers

International audienceLet X={xi:1≤i≤n}⊂N+X={xi:1≤i≤n}⊂N+, and h∈N+h∈N+. The h-iterated sumset of X , denoted hX , is the set {x1+x2+...+xh:x1,x2,...,xh∈X}{x1+x2+...+xh:x1,x2,...,xh∈X}, and the [h][h]-sumset of X , denoted [h]X[h]X, is the set View the MathML source⋃i=1hiX. A [h][h]-sumset cover of S⊂N+S⊂N+ is a set X⊂N+X⊂N+ such that S⊆[h]XS⊆[h]X. In this paper, we focus on the case h=2h=2, and study the APX-hardproblem of computing a minimum cardinality [2]-sumset cover X of S (i.e. computing a minimum cardinality set X⊂N+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 sourceO(2(3logk−1.4)kpoly(k)) time, and thus outperforms the O(5k2(k+3)2k2log(k)) time FPT result presented in Fagnot et al. (2009) [6]. Second, we show that deciding whether a set S has a smaller [2]-sumset cover than itself is NP-hard