2
$\begingroup$

I know that finding the Maximum clique of a graph is NP-Complete. However, is there a fast algorithm or trick exists which would allow me to just calculate the Clique number of a graph without actually bothering about what are those vertices?

Also, does it make any difference, if the graph has some special properties? For example, if the graph is known only to have triangles as building blocks or no cycles at all. In other words, there would not be any cycle which does not have an embedded triangle inside.

P.S. I have not written any code to start with as it would be pointless to try and solve and NP-complete problem. However, as this problem is a common problem, and if there exists a faster algorithm which gives me only the Clique number of a graph, I would like to understand that algorithm first then I will try to do some hands on.

$\endgroup$
3
$\begingroup$

Finding just the clique number is also NP-hard.

If a graph is chordal (which is perhaps what you mean in the other question) then the maximal clique can be found in polynomial time by traversing the perfect elimination order.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ perfect elimination order? Could you please give an example? thanks. $\endgroup$ – user3243499 Jul 14 '18 at 13:39
  • $\begingroup$ Search for chordal graph in any book on graph theory or even wikipedia. $\endgroup$ – Michal Adamaszek Jul 14 '18 at 14:07
  • $\begingroup$ Got it, thanks. $\endgroup$ – user3243499 Jul 16 '18 at 11:30

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.