Partitioning a set based on binary predicate

Question

Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which partitions the set as:

$X= \bigcup X_j$

such that for any $j$ it holds that $F(x_k,x_l) = 1$ if $x_k,x_l \in X_j$ and $F(x_k,x_s) = 0$ if $x_k \in X_j \land x_s \notin X_j$ (boolean values are being used at True/False).

My initial guess was to use a divide and conquer algorithm but was not able to find a merging algorithm which would make the divide-and-conquer strategy worth it in terms of complexity gain. I imagine this is a standard problem but I am not sure where to look for a solution or if such a solution exists for an arbitrary binary predicate.

Answer 1

There is no deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$. One can prove this with an adversarial argument.

Consider running the algorithm on the following input:

• Input #1: $F(x_i,x_i)=1$, and $F(x_i,x_j)=0$ if $i \ne j$.

Keep track of the sequence of pairs $(x_i,x_j)$ of objects that $F$ is evaluated on before it terminates. If the running time of the algorithm is is $o(N^2)$, then for some sufficiently large $N$ the algorithm must make strictly fewer than $N^2-N$ queries to $F$, so there must be some pair of objects that it doesn't evaluate $F$ on, say $F(x_3,x_7)$. But then consider running the algorithm on the following input:

• Input #2: Same as input #1, except that $F(x_3,x_7)=1$.

Since the algorithm does not evaluate $F(x_3,x_7)$, the algorithm cannot distinguish these two inputs, and must produce the same output on Input #1 and Input #2. However, the correct answer is different for these two inputs. This means that the algorithm's output will be incorrect for at least one of these two inputs.

Therefore, any deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$ is not correct on all inputs.