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:
- $J\subseteq I$
- $a_j \in A_j, \forall j \in J$
- $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:
- $f(i)\in A_i$ for all $i \in I$ where $f$ is defined.
- $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?
