Splitting set into subsets by criterion

Question

I am looking for an algorithm that will split a set $A = \{ a_1, a_2, ..., a_N \}$ into (possibly) multiple subsets based on a given criterion. In my case, the criterion is spatial overlap of the elements in the set, but it could be any criterion really. Let's define a function $crit(a_1, a_2)$ which takes as input two elements of $A$ and outputs a boolean indicating whether those two elements overlap.

If $crit(a_i, a_j) = false$ for all $a_i, a_j \in A$, then the output of the algorithm should be a single set containing all of the elements of $A$. If $crit(a_i, a_j) = true$ for a single pair of elements $a_i, a_j \in A$, then the output of the algorithm should be two sets, one set containing all elements except for $a_i$, and one set containing all elements except for $a_j$. We continue this pattern until we reach the other extreme case, in which $crit(a_i, a_j) = true$ for all $a_i, a_j \in A$, in which case the output of the algorithm should be a partition of $A$: $N$ sets, each containing a single element from $A$.

I would be surprised if this problem has not been formalized before. Is there an efficient algorithm for solving this problem?

Edit: For clarification, it is ok if an element ends up in multiple sets in the output. In fact, an element should be in every set that does not contain an element that overlaps with it. For example, if $A = \{ w,x,y,z\}$, $crit(w, x) = true$, $crit(w, y) = false$, $crit(w, z) = true$, $crit(x, y) = false$, $crit(x, z) = false$, $crit(y, z) = false$, then the output should be $A' = \{ \{ w, y \}, \{ x, y, z \} \}$.

Another edit: based on bbejot's response, I did a bit more looking and it does appear that I can reduce my problem to enumerating all maximal cliques of the graph represented by the adjacency matrix bbejot describes in his response. In response to my original question, there is no efficient algorithm for solving this problem, but the Bron–Kerbosch algorithm seems to be pretty standard.

Answer 1

I believe there are two interpretations of your criterion. One interpretation is easily solvable, and the other is NP-Complete.

First, a greedy algorithm for what you describe: Let $A_1$, $A_2$, ..., $A_N$ all start as the empty set.
Loop through each $a_i \in A$.
Put $a_i$ in the first $A_k$ such that for each $a_j$ already in $A_k$, $crit(a_i, a_j) = false$.
After looping through all the elements of $A$, disregard any $A_i$ which is still empty.

This greedy algorithm holds in the three examples you give.

A second interpretation is: "Let the set $A_i$ be as large as possible but not including any elements from $A_1$ to $A_{i-1}$". Let $A'$ be an $N \times N$ matrix where $A_{i, j}'$ is 1 if $crit(a_i, a_j) = false$ and 0 otherwise. Then finding $A_1$ is exactly finding the maximum clique of a digraph with adjacency matrix $A'$. This, of course, makes the problem NP-Hard.

Let's hope you only need the first.