The CLIQUE NUMBER problem is NP Complete (due to correspondence with $3$-SAT); so is the INDEPENDENCE NUMBER problem (since $\omega(\overline{G}) = \alpha(G)$, or from CHROMATIC NUMBER problem). Can anything be said about the complexity of finding $\alpha(G) + \omega(G)$ ?
Since $\omega(\overline{G}) = \alpha(G)$, I am considering two related parameters, in fact, opposite in nature. I can have upper and lower bounds due to Nordhus-Gaddum relations, but I want to study the complexity results.
Thanks in advance.
It's easy to see that computing $\alpha(G) + \omega(G)$ (for general $G$) is equivalent to computing $\alpha(G)$: given any graph $G$, construct $G'$ as the disjoint union of $G$ with $K_n$ where $n$ is the number of vertices of $G$. Then we easily have $\omega(G') = n$ and $\alpha(G') = 1 + \alpha(G)$, so if you could compute $\alpha(G') + \omega(G')$...
Likewise, if you can compute $\alpha(G)$ in general, then you probably already know how to compute $\alpha(G) + \omega(G)$.