1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ May 18, 2011 at 15:12
  • $\begingroup$ 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. $\endgroup$
    – user2582
    May 18, 2011 at 15:18
  • $\begingroup$ @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. $\endgroup$ May 18, 2011 at 15:20
  • $\begingroup$ @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. $\endgroup$ May 18, 2011 at 15:21
  • $\begingroup$ 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. $\endgroup$
    – bbejot
    May 18, 2011 at 16:44

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ May 18, 2011 at 15:29
  • $\begingroup$ 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! :( $\endgroup$ May 18, 2011 at 15:47
  • $\begingroup$ @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. $\endgroup$
    – bbejot
    May 18, 2011 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.