Question

Let $\mathbf{HALF}-\mathbf{CLIQUE}=\{<\mathbf{G}>|\mathbf{G}$s an undirected graph having a complete subgraph with at least$\mathbf{m}/\mathbf{2}$ nodes, where m is the number of nodes in$\mathbf{}\mathit{G}$. Show that HALF-CLIQUE is NP-complete.

Short answer

The clique is $k$a clique of $g$, and hence$⟨G,k⟩\in CLIQUE.$

Step-by-step solution

Step 1:Undirected graph of the nodes

$HALF-CLIQUE\in NP:$

Let N be the nondeterministic polynomial time (NTM) that decides $HALF-CLIQUE$in polynomial time.

N can be described as follows:

$N=\text{'}\text{'}on input graph ⟨G⟩:$

Non-deterministically choose at least$n/2$ nodes

Verify whether$n/2$ nodes form a clique

If they form a clique then accept.

Otherwise, reject".

Therefore,$HALF-CLIQUE\in NP$

$CLIQUE{⩽}_{p}HALF-CLIQUE:$

A reduction from $C L I Q U E$ to $H A L F-C L I Q U E$ as follows:

On input $⟨G,k⟩,where \text{G}$is a graph on n verifies and k is an integer:

Step 2:Size of the Half-Clique

When $k<n/2$G has a $k$-clique, then $G$has a clique of size.

$k+\left(n-2k\right)=\left(2n-2k\right)/2$

width="197">k+n-2k=2n-2k/2

Therefore, the HALF-CLIQUE is NP- complete.