1
$\begingroup$

Costas array is a set of $n$ points lying on the square of a $n×n$ checkerboard, such that each row or column contains only one point, and that all of the $n(n − 1)/2$ displacement vectors between each pair of dots are distinct.

I am interested in the computational problem of finding Costas arrays with some specified displacement vectors.

What is the complexity of deciding the existence of Costas array when given as input a subset of the $n(n − 1)/2$ displacement vectors? Is this problem NP-complete? Has anyone studied this computational problem before?

Improve this question
$\endgroup$
1
  • $\begingroup$ Absence of evidence is a poor evidence of absence. However, for the related notion of Sidon sets, I am not aware of any published work. In that related setting, there are several open problems related to possibility of extension of partial Sidon sets, which suggests that the computational is likely to be hard. $\endgroup$
    – Boris Bukh
    Commented Dec 14, 2018 at 14:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .