Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Is "non-transitive" a restrictive condition, or do you just mean that $R$ is not guaranteed to be transitive? – Henning Makholm Apr 6 '13 at 15:32
its restrictive condition – Tomáš Šíma Apr 6 '13 at 15:59
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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