Consider the class of simple connected n/2-regular graphs, n even. Are the maximum clique problem and/or maximum independent set problem NP-complete on such graphs? Is there any known result which would imply NP-completeness or, otherwise, how can it be proved/disproved? Any helpful information comment would be highly appreciated.



Problem NP-completeness on a specific graph class
The answer is **yes**.


By taking complements, the maximum clique problem can be reduced to the maximum independent set problem (MIS) on graphs with degree $n/2-1$.


It is NP-hard to approximate MIS to within a factor of $7/6$, even for bounded degree graphs. (see [On the Hardness of Approximating Minimum Vertex Cover](https://www.jstor.org/stable/3597377), p.449.) Assume that approximating MIS on a graph $G$ with maximum degree $c$ to within a factor of $7/6$ is NP-hard.


Let $H\_1$ and $H\_2$ be graphs constructed from $G$. Both $H\_1$ and $H\_2$ have vertex set $\{(x,0)|x \in V(G)\}$ $\cup$ $\{(x,1)|x \in V(G)\}$. In both $H\_1$ and $H\_2$, $(x,0) \sim (y,0) \wedge (x,1) \sim (y,1)$ iff $x \sim y$ in $G$; otherwise $(x,0) \not \sim (y,0)$ and $(x,1) \not \sim (y,1)$. In $H\_1$, $(x,0) \sim (y,1) \wedge (x,1) \sim (y,0)$ iff $x \not \sim y$ in $G$; In $H\_2$, $(x,0) \sim (y,1) \wedge (x,1) \sim (y,0)$ iff $x \not \sim y$ in $G$ and $x \neq y$. Otherwise $(x,0) \not \sim (y,1) \wedge (x,1) \not \sim (y,0)$ in the respective graphs.


The graph $H\_1$ has vertex count $2|G|$ and degree $|G|$, and the graph $H\_2$ has vertex count $2|G|$ and degree $|G|-1$. Let $n=2|G|$, and $H\_1$ has vertex count $n$ and degree $n/2$, $H\_2$ having vertex count $n$ and degree $n/2-1$. Now I will show that MIS is hard on either graph by transferring a solution of MIS on $H\_1$ or $H\_2$ to an approximate solution of MIS on $G$.


If $I$ is a maximum independent set of $H\_1$ or $H\_2$, then $\{x:(x,0) \in I\}$ and $\{x:(x,1) \in I\}$ are both independent sets of $G$. One of them has size at most $c+1$ and thus the other has size at least $\alpha(H)-(c+1)$. (Here $H$ means either $H\_1$ or $H\_2$.) So $\alpha(H) - (c+1) \leq \alpha(G) \leq \alpha(H)$. This means for all $|G| \geq 7(c+1)$, we have a $7/6$-approximate solution of MIS on $G$.


