How to get the maximal fully related subset of a partially related set? I have a finite partially related set $S$ with a relation R that is 


*

*Irreflexive: $x\,!R\,x$ $\forall\,x\in S$

*Symmetric: $x\,R\,y\iff\,y\,R\,x\,\,\forall\,x,y\in S$

*May or may not be transitive: $x\,R\,y$ and $y\,R\,z$ does not imply $x\,R\,z\,\,\forall\,x,y,z\in S$
I want to know if there is a systematic way to get a maximal subset M of S that is fully related. By fully related I mean that $\forall\,x,y\in M$, $x\,R\,y$, by maximal I mean that $\nexists\,z\in S\,|\,z\,R\,x\,\forall\,x\in M$
 A: This problem is usually phrased in the language of graphs rather than relations. In this language, your "fully related" subsets are cliques in a simple graph.
Finding a maximal clique (that is, one that can't be extended) is easy enough -- just iterate through your set in some arbitrary order and add each element to your clique unless it fails to be connected to one of the elements you have already added. This can take $O(|S|^2)$ time, but that's also the time it will take you to even read a description of an arbitrary $R$, so that's to be expected.
However, if you want to find a largest possible clique, that is hard -- in fact, determining whether there even is a clique of a given size is one of the classical NP-complete problems.  This means that no practically feasible general algorithm is known, and none is expected to exist.
(Of course, it is easy to come up with some algorithm: Iterate through all possible subsets of $S$ and check whether each of them is a clique. The trouble is that this can become prohibitively slow if $S$ has more than a few dozen elements).
