CODEWITHSUNDEEP
algorithm
Ryan C. Thompson
Ryan C. Thompson

Reputation: 42010

Finding that maximal subset of items with a minimum distance between them?

My problem is similar to this one: Get largest Subset of Integers with certain minimum distance/difference

However, in my case, rather than distances between integers, which are embeddable in one dimension, I have an arbitrary set of elements and a distance matrix that gives the distance from each element to each other element. The distances are all integers and they satisfy the requirements of a distance metric. Given a specified minimum distance (e.g. 3), the goal is to identify the maximum-sized subset of the starting set such that every pair of elements in the subset has a distance of at least the specified threshold.

According to the link above, the obvious greedy algorithm is optimal for the one-dimensional case (distances between integers). However, I doubt that this is the case for an arbitrary number of dimensions. This seems like the kind of problem that would reduce to some well-known computer science problem, but if it is, I haven't been able to find the right combination of keywords to identify it. I have only found references to the one-dimensional case.

So, is this problem NP-complete? If so, is there a good heuristic algorithm? If not, is there a fast algorithm for solving it optimally?

(For anyone curious, this problem arose in the context of choosing the largest possible set of DNA sequencing barcodes that are sufficiently different from each other than they can still be distinguished even with sequencing errors.)

Edit: Now that I think about it, we can simplify the problem by replacing the distance matrix with a matrix of 0 and 1s, where 1 means the elements are close (distance less than the threshold) and 0 means the elements are not close. Then I suppose the goal is to find the maximum-sized subset of elements whose adjacency matrix is all 0s.

Upvotes: 2

Views: 1119

Answers (1)

mcdowella
mcdowella

Reputation: 19601

I think the problem you need is https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29, which is NP-complete. If you can solve your problem for minimum allowable distance 2, then you can solve maximum independent set, by constructing a distance matrix where the distance between nearby vertices in the independent set graph is 1, so that they are not allowed together.

Upvotes: 2

Related Questions