0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.