Integer sets with forbidden differences Given a finite set $S$ of positive integers, and a positive integer $n$, let $F(n,S)$ be the largest possible cardinality of a subset of {$1,2,\dots,n$} no two of whose elements differ by a number in $S$.
E.g., if $S=${$2,3$} and $n=10$, we have $F(n,S)=4$ corresponding for instance to the set {$1,2,6,7$}.
What is known about the computational complexity of $F$?
A purely greedy approach doesn't work. E.g., if $S=${$3,5$} and $n=20$, a greedy approach gives the set {$1,2,3,9,10,11,17,18,19$} which has smaller cardinality than {$1,3,5,7,9,11,13,15,17,19$}.
Dynamic programming works, but takes computational resources that are exponential in max($S$). Can one do better?
I don't like the name of this question; if anyone can think of a better way to describe the problem, please feel free to revise it.
 A: Here is one way to view this problem:
Form the graph $G$ with vertices $\{1,\dots,n\}$ and edges $(i,j)$ for all $i,j$ such that $|i-j|\in S$. Then $F(n,S)$ is the size of a maximal independent set in $G$. 
From this it is clear $F$ has at most the computational complexity of finding the size of a maximal independent set. It is not quite clear to me how to use the special properties of this graph to get something better.
For special sets $S$, one immediately gets the value $F(n,S)$:


*

*$F(n,\{k\})=\sum_{i=1}^{k+1}\lfloor\frac{n+k+i-1}{2k}\rfloor$

*$F(n,\{1,\dots,k\})=\lceil\frac{n}{k+1}\rceil$


For your two examples the graphs look like this:

.
All instances for $F(10,\{2,3\})=4$ are:

$\{1, 2, 6, 7\}, \{1, 2, 6, 10\}, \{1, 2, 7, 8\}, \{1, 2, 8, 9\}, \{1, 2, 9, 10\}, \{1, 5, 6, 10\}, \{1, 5, 9, 10\}, \{2, 3, 7, 8\}, \{2, 3, 8, 9\}, \{2, 3, 9, 10\}, \{3, 4, 8, 9\}, \{3, 4, 9, 10\}, \{4, 5, 9, 10\}$

All instances for $F(20,\{3,5\})=10$ are:

$\{1, 3, 5, 7, 9, 11, 13, 15, 17, 19\}, \{2, 4, 6, 8, 10, 12, 14, 16, 18, 20\}$

