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

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

<p>This greedy algorithm holds in the three examples you give.</p>

<p>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&#39;$ be an $N \times N$ matrix where $A_{i, j}&#39;$ 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&#39;$.  This, of course, makes the problem NP-Hard.</p>

<p>Let's hope you only need the first.</p>

CC BY-SA 3.0
2011-05-18T15:29:50.470Z
Luckily, I think what I'm looking for is the first algorithm you listed. It is indeed easy and intuitive, I just couldn't figure it out. Thanks!
Daniel Standage
CC BY-SA 3.0
2011-05-18T15:47:24.573Z
Actually, looking at your first algorithm more closely, it doesn't solve the second example I gave. Either that or I'm not understanding it correctly. It also doesn't work for the example I just added in my update, nor the first example from the comments on the original post. Maybe I am indeed looking for the solution to an NP-Hard problem! :(
Daniel Standage
CC BY-SA 3.0
2011-05-18T16:40:33.147Z
@Daniel, ah yes, I was thinking that all answers were to be partitions.  Your comment about listing all maximal cliques seems to cover what you want.
bbejot
CC BY-SA 3.0
2011-05-18T15:07:04.413Z
2011-05-18T15:07:04.413Z
bbejot
<p>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.</p>

<p>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$.</p>

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

<p><strong>Edit:</strong> 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&#39; = \{ \{ w, y \}, \{ x, y, z \} \}$.</p>

<p><strong>Another edit</strong>: 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 <em>efficient</em> algorithm for solving this problem, but the <a href="http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm" rel="nofollow">Bron–Kerbosch algorithm</a> seems to be pretty standard.</p>

CC BY-SA 3.0
2011-05-18T15:12:20.173Z
If A={a,b,c}, crit(a,b)=crit(b,c)=false and crit(a,c)=true what is the output? If you give a "priority" to true (i.e. split if two elements overlap) then the algorithm seems trivial. Perhaps I didn't understand well the problem, can you give a more complete example?
Marzio De Biasi
CC BY-SA 3.0
2011-05-18T15:18:26.307Z
I am not sure if I have understood correctly your problem but I think that you could model each element as a vertex. Two vertices $v_1,v_2$ are adjacent if $crit(v_1,v_2) = true$. Hence, if there are two vertices adjacent, you want it in different sets right? So you need to start from each vertex and gets a maximum-independent-set which contains that vertex. However there could be many of them so which one you want? I think it would be great if you can clarify your problem. Hope it helps.
user2582
CC BY-SA 3.0
2011-05-18T15:20:29.933Z
@Vor In your example, the output would be A' = { {ab}, {bc} }. As far as being trivial, I'm a biologist, so although I am experienced with formulating problems mathematically and (to some extent) programming, my training has not exposed me to as many algorithms as, say, your average computer scientist.
Daniel Standage
CC BY-SA 3.0
2011-05-18T15:21:42.787Z
@Vor @user2582 I will go ahead and clarify (for posterity's sake), but I think bbejot's first answer is what I was looking for.
Daniel Standage
CC BY-SA 3.0
2011-05-18T16:44:28.447Z
May I ask what this is for?  What actually are the $a_i$'s and why to they spatially overlap?  Perhaps we can change the problem to something computationally easier.
bbejot
CC BY-SA 3.0
2011-05-18T17:38:24.947Z
@bbejot The elements of the set are genes: each gene has a start position and an end position with respect to a sequence of genomic DNA, so overlap is easily defined. I want to compare two sets of gene predictions, but the comparison assumes that genes from the same set do not overlap (though I find this in data sometime). Basically I need to make sure that each set has no overlap, and it looks like the best (only?) way to do that is to divide each of the two sets into multiple subsets (maximal cliques) and compare every maximal clique from one set with every maximal clique from the other set.
Daniel Standage
CC BY-SA 3.0
2011-05-18T18:08:47.733Z
Ok, let me repeat this back to you in computational terms to see if I am understanding.  Each gene can be represented as a list of items.  "Size of Overlap" is defined as the last $k$ items of one list being identical to the first $k$ items of another list.  We have some tolerance for how large this overlap can be.  We want to verify that a set of lists contains no pair with an overlap above our tolerance.  Is this right?
bbejot
CC BY-SA 3.0
2011-05-18T18:27:52.393Z
@bbejot No, each gene is not represented as a list of items, each _set_ of genes is represented as a list. We want to verify that each set contains no pair with any overlap whatsoever (remember the boolean criterion function).
Daniel Standage
CC BY-SA 3.0
2011-05-19T19:35:40.783Z
I think the problem is formulated in wrong language. All that you have is one set and one [binary] relation. The expected output is a set of sets. Now a set can be represented as a relation and the output is a relation too. So you essentially have a [binary] operation over two relations. Which one?
Tegiri Nenashi
<ds.algorithms>
Splitting set into subsets by criterion
Daniel Standage
# Splitting set into subsets by criterion

(Asked by: username_0 on 2011-05-18)

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 username_3'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 username_3 describes in his response. In response to my original question, there is no *efficient* algorithm for solving this problem, but the [Bron–Kerbosch algorithm](http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm) seems to be pretty standard.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: If A={a,b,c}, crit(a,b)=crit(b,c)=false and crit(a,c)=true what is the output? If you give a "priority" to true (i.e. split if two elements overlap) then the algorithm seems trivial. Perhaps I didn't understand well the problem, can you give a more complete example?  
> **username_2**: I am not sure if I have understood correctly your problem but I think that you could model each element as a vertex. Two vertices $v_1,v_2$ are adjacent if $crit(v_1,v_2) = true$. Hence, if there are two vertices adjacent, you want it in different sets right? So you need to start from each vertex and gets a maximum-independent-set which contains that vertex. However there could be many of them so which one you want? I think it would be great if you can clarify your problem. Hope it helps.  
> **username_0**: @Vor In your example, the output would be A' = { {ab}, {bc} }. As far as being trivial, I'm a biologist, so although I am experienced with formulating problems mathematically and (to some extent) programming, my training has not exposed me to as many algorithms as, say, your average computer scientist.  
> **username_0**: @Vor @username_2 I will go ahead and clarify (for posterity's sake), but I think username_3's first answer is what I was looking for.  
> **username_3**: May I ask what this is for?  What actually are the $a_i$'s and why to they spatially overlap?  Perhaps we can change the problem to something computationally easier.  
> **username_0**: @username_3 The elements of the set are genes: each gene has a start position and an end position with respect to a sequence of genomic DNA, so overlap is easily defined. I want to compare two sets of gene predictions, but the comparison assumes that genes from the same set do not overlap (though I find this in data sometime). Basically I need to make sure that each set has no overlap, and it looks like the best (only?) way to do that is to divide each of the two sets into multiple subsets (maximal cliques) and compare every maximal clique from one set with every maximal clique from the other set.  
> **username_3**: Ok, let me repeat this back to you in computational terms to see if I am understanding.  Each gene can be represented as a list of items.  "Size of Overlap" is defined as the last $k$ items of one list being identical to the first $k$ items of another list.  We have some tolerance for how large this overlap can be.  We want to verify that a set of lists contains no pair with an overlap above our tolerance.  Is this right?  
> **username_0**: @username_3 No, each gene is not represented as a list of items, each _set_ of genes is represented as a list. We want to verify that each set contains no pair with any overlap whatsoever (remember the boolean criterion function).  
> **username_4**: I think the problem is formulated in wrong language. All that you have is one set and one [binary] relation. The expected output is a set of sets. Now a set can be represented as a relation and the output is a relation too. So you essentially have a [binary] operation over two relations. Which one?  

---

## 1 answers

### Answer by username_3 on 2011-05-18. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Luckily, I think what I'm looking for is the first algorithm you listed. It is indeed easy and intuitive, I just couldn't figure it out. Thanks!  
> **username_0**: Actually, looking at your first algorithm more closely, it doesn't solve the second example I gave. Either that or I'm not understanding it correctly. It also doesn't work for the example I just added in my update, nor the first example from the comments on the original post. Maybe I am indeed looking for the solution to an NP-Hard problem! :(  
> **username_3**: @Daniel, ah yes, I was thinking that all answers were to be partitions.  Your comment about listing all maximal cliques seems to cover what you want.  

---

