# Does the intersection of VC and CLIQUE belong to NPC?

Define: $$L=\{(G,k) : G\text{ has a vertex cover of size at most k, and a clique of size at least k}\}$$

I need to determine whether $$L\in \mathrm{NPC}$$ or $$L\in \mathrm{P}$$. I suspect that $$L\in \mathrm{NPC}$$, been trying to prove it by looking for a reduction from Vertex Cover, but couldn't find one.

The graphs with clique size at least $$k$$ and VC at most $$k$$ have a particular structure: They can be partitioned into three sets, $$C$$, $$I$$ and a singleton $$\{s\}$$; $$G[C]$$ is a clique, $$G[I]$$ is an independent set and $$s$$ is just a vertex. $$G[C \cup I]$$ is what's called a split graph.
Proof: If a graph $$G$$ contains a clique of size $$k$$, then that clique uses up (at least) $$k-1$$ of your vertex cover budget. Let $$G,k$$ be a yes instance and $$C$$ any $$k$$-clique. Observe that $$G - C$$ is a star with possibly isolated vertices.
There are two cases: $$G-C$$ has edges, and $$G-C$$ does not have edges. The latter case is trivial, since we can let $$C$$ be the solution. In the former case, $$G-C$$ is the star graph with isolates. Let $$s$$ be the vertex with non-zero degree.
Both these cases lead to polynomial recognition algorithm. The one in which $$G-C$$ is an independent set, is the case where $$G$$ is a split graph. The other case has one vertex $$s$$ for which $$G-s$$ is a split graph. Guess $$s$$, and you're back at case 1.
As xskxzr pointed out, there is not necessarily a unique "split partition", that is, a partitioning of a split graph into the vertex sets $$C$$ and $$I$$, however, there are at most $$n$$ such partitions, and you can try all. This leads in the end to an $$O(n^3m)$$ algorithm for VC∩C, which I'm sure can be improved.
• If I understand you correctly, the reduction would be to add a clique of size $k$. but then if I use $k'=2k-1$ I would need a clique of size $2k-1$, and that's a problem. – John Apr 22 '19 at 13:35