# Karp hardness of a clique with given number of outer-incident edges

A clique in an undirected graph $$G(V,E)$$ is a subset of vertices $$\mathcal{C}\subseteq V$$ every pair of which is adjacent $$u,v\in \mathcal{C}\implies uv\in E(G)$$.

Given a clique $$\mathcal{C}\subseteq V(G)$$ in a graph $$G$$, an outer-incident edge of $$\mathcal{C}$$ is an edge $$uv\in E$$ with $$u\in \mathcal{C}$$ and $$v\not\in\mathcal{C}$$. In other word, an outer-incident edge is an edge connecting one vertex in the clique with one other outside of the clique.

Our problem $$\mathrm{CLIQUE}$$-$$\mathrm{OUTWARD}$$-$$\mathrm{EDGES}$$ is formally defined as:

Input: An undirected graph $$G(V,E)$$ and a natural number $$k$$

Output: YES if $$G$$ has a clique $$\mathcal{C}\subseteq V$$ such that $$\mathcal{C}$$ has exactly $$k$$ outer-incident edges, otherwise NO

The question is what the complexity of $$\mathrm{CLIQUE}$$-$$\mathrm{OUTWARD}$$-$$\mathrm{EDGES}$$ is.

Our problem is $$NP$$-complete by a reduction from Exact Cover by $$3$$-sets ($$\mathrm{X3C}$$).

Given an $$X3C$$ instance with the universe set $$U=\{e_1,e_2,\cdots,e_n\}$$ and collection of $$3$$-sets $$\mathcal{C}=\{s_1,s_2,\cdots,s_m\}$$, we create an undirected graph $$G$$ as follows.

For each element $$e_i$$, create a vertex (which will be referred to by the same name).

For each $$3$$-set $$s_j$$, create a vertex (which will also be referred to by the same name).

Connect $$e_i$$ and $$s_j$$ whenever $$e_i\in s_j$$.

Connect $$s_{j_1}$$ and $$s_{j_2}$$ whenever they are disjoint.

Pick some large enough $$M$$, connect each set-vertex to dummy vertices to make sure that every set-vertex is of degree $$M$$.

Call the obtained graph $$G$$. Now, set $$k=n+(M-3-\frac{n}3+1)*\frac{n}3$$. The reduction then outputs an instance, namely $$(G,k)$$.

Suppose there exists an exact cover for the $$X3C$$ instance, we can easily form a solution to our problem by taking all the set-vertices of the exact cover. Clearly, this is a clique since every pair of $$3$$-sets in an exact cover needs to be disjoint. It has exactly $$k$$ outer-incident edges.

Conversely, if there exists a clique with $$k$$ outer-incident edges then every vertex of this clique needs to be set-vertex. Indeed, if there is any element-vertex in the clique, then the size of the clique is equal to the number of $$3$$-sets that includes that element plus one (the element-vertex itself). But then the size of this clique is only $$4$$, since $$X3C$$ is still $$NP$$-complete when each element is included in at most three $$3$$-sets. So, this is a clique of set-vertices. Thus, they are pairwise-disjoint. With $$k$$ outer-incident edges, the size of this clique must be exactly $$\frac{n}3$$. This is due to the fact that $$M$$ can be large enough (still polynomially) so that the binomial defining $$k$$ (in variable $$x$$, the size of the clique) is monotone in $$[1,\cdots,m]$$.