In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here.

In the second page of the introduction he states the following lemma.

Let $G = (V,E)$ be a graph and $S \subseteq V.$ Then $$ ||G|| = \max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\} $$

where $||G||$ is the size of the maximum clique in $G$ and $A(C)$ is the set of adjacent vertices to one or more elements in $C$.

This does not make sense to me, for example if we let $S$ be the set containing just one isolated vertex, then $\max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\} = 1$, since $A(C) \setminus S = \emptyset \setminus S = \emptyset$.

Even worse, we can take $S = \emptyset$ and then the lemma falls apart.

What am I missing?


You definition of $A(C)$ is wrong. It is the set of vertices adjacent to all vertices in $C$: $$ A(C) = \{ v \in V : \forall u \in C, (u,v) \in E \}. $$ In particular, if $C = \emptyset$ then $A(C) = V$.

In your example, suppose that $S = \{v\}$. Let's see what $|C| + \|G_{A(C) \setminus S}\|$ amounts two for all choices of $C$:

  1. If $C = \emptyset$, then $A(C) \setminus S = V \setminus \{v\}$, and so $|C| + \|G_{A(C)\setminus S}\|$ is the maximum size of a clique in $G$ that doesn't contain $v$.
  2. If $C = \{v\}$, then $A(C) \setminus S = N(v)$, the set of neighbors of $v$. Therefore $|C| + \|G_{A(C) \setminus S}\|$ is the maximum size of a clique in $G$ that contains $v$.

So in this case, the formula is correct.

When $S = \emptyset$, the formula just states that $\|G\| = \|G\|$.


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.