Algorithm to get maximal selection set of a collection of sets with a binary relation

Question

I have a finite collection of finite sets $\{A_i\}_{i \in I}$. There is a relation $R$ defined on the elements of those sets (which is not transitive, it is irreflexive, and it is symetric). Suppose we define a related partial choice as a set $\{a_j\}_{j\in J}$ such that:

1. $J\subseteq I$
2. $a_j \in A_j, \forall j \in J$
3. $a_j R a_{j'} \forall j,j' \in J$

That is, it consists of choosing one element for each of some of the original sets, such that all elements are related to each other.

What I need is an algorithm that a computes a related partial choice with maximum cardinality.

An equivalet way of seeing the problem would be as follows. Given the set $\{A_i\}_{i \in I}$, call a related selection partial function ($RSPF$, for short) any partial function $f : I \rightarrow \cup_{i\in I} A_i$ such that:

1. $f(i)\in A_i$ for all $i \in I$ where $f$ is defined.
2. $f(i)Rf(i')$ for all $i,i' \in I$ where f is defined.

If we define $N := max(\{ \#Dom(f) : f \in RSPF\})$. I need an algorithm to efficiently compute an $f$ such that $\#Dom(f) = N$.

In the algorithm, the $\{A_i\}_{i \in I}$ sets can be arrays or sets.

Any Ideas?

Answer 1

Your problem generalizes MAX-CLIQUE, and as such its decision version is NP-complete. To see this, given a graph $G=(V,E)$, take $I=V$, $A_i=V$, and $R=E$.