Maximum number of elements, where no two are in relation

Question

I have a set S. I have reflexive, symmetric and non-transitive relation R on SxS.

I have to find size of set P, which is the biggest subset of S where :

Any two distinct elements of P are not in relation R.

Any idea how to solve this in better way then brute-forcing? I think, I can put elements of S into graph and use some kind of graph algorithm, but I am completely lost here. Notice, I only need size of P, not elements of P.

Answer 1

Note that $(S,R)$ already is an undirected graph, with $S$ being the set of vertices and $R$ the edges, if you decide to ignore the self-loops that ariese from $R$ being reflexive.

What you're looking for is a maximal clique in the complementary graph $(S,(S\times S) \setminus R)$. Finding even the size of a maximal clique is a well known NP-complete problem, so you shouldn't hope to find an algorithm that's significantly better than brute force.