9
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Perhaps "Picking many integer points in $1$-dimensional lattice-polytope, while avoiding certain distances" $\endgroup$
    – Moritz Firsching
    Commented Feb 26, 2016 at 20:44
  • 2
    $\begingroup$ Or: "Integer sets with forbidden differences." $\endgroup$
    – Joseph O'Rourke
    Commented Feb 28, 2016 at 14:20
  • $\begingroup$ What if instead of $\{1,\ldots,n\}$ we can only select elements from some $X$ subset of it (that is given as part of the input)? There is a better chance for hardness results maybe. And of course you must know, but let me also mention that if $S$ has only odd integers, then the graph is bipartite and thus we can solve the problem in polynomial time. $\endgroup$
    – domotorp
    Commented Mar 2, 2016 at 20:09

1 Answer 1

Reset to default
3
$\begingroup$

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:

n=10, S=(2,3) n=20, S=(3,5).

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\}$

Improve this answer
$\endgroup$
1
  • $\begingroup$ this was answered before the question was edited to be more specific $\endgroup$
    – Moritz Firsching
    Commented Mar 14, 2016 at 19:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .