2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great hint. Do you have any pointer to a state-of-the-art approximation algorithm to solve MAX-CLIQUE? just to see if I can generalize it and use it. $\endgroup$ – eguaio Dec 16 '16 at 16:55
  • 1
    $\begingroup$ Wikipedia probably has a link. However, their worst-case performance is abysmal: they only promise an $O(n/\log n)$ approximation, if I remember correctly. This is unavoidable since it is NP-hard to do a $O(n^{1-\epsilon})$ approximation for any $\epsilon > 0$. I suggest looking into heuristic algorithms. $\endgroup$ – Yuval Filmus Dec 16 '16 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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