Problem NP-completeness on a specific graph class

Question

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.

Answer 1

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, 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$.