# NP-hardness language

How to prove that language $$L = \{G \; | \; \omega(G) \geq \frac{9}{10}\cdot n\}$$, where $$n$$ - number of vertices in the graph, NP-hard?

$$\omega$$ - is a clique number.

Consider the following reduction from the NP-complete problem $$Clique = \{ \langle G, k\rangle \ : \text{G is undirected Graph that has a clique of size at least k}\}$$ to $$L$$. The reduction operates as follows.

Given input $$\langle G = (V, E), k \rangle\in Clique$$:

1. If $$k < \frac{9\cdot|V|}{10}$$, output $$G' = G \cup K_{t}$$, where $$t= 9\cdot |V| -10k$$, and $$K_t$$ is the complete graph over $$t$$ vertices. In addition, add edges that connect every vertex in $$K_{t}$$ with every vertex in $$G$$.

2. Othwerwise, if $$k \geq \frac{9\cdot|V|}{10}$$, output $$G'$$ that is defined as follows. $$G'$$ is obtained by replacing each vertex of $$v \in V$$ by a clique of size 9, denoted $$c_9(v)$$, and then for every edge $$\{ u, v\}\in E$$, the two cliques $$c_9(v), c_9(u)$$ in $$G'$$ are connected, that is, every vertex of $$c_9(v)$$ is connected by an edge with every vertex of $$c_9(u)$$. Also, add to $$G'$$ new $$t$$ isolated vertices, where $$t= 10k - 9|V|$$.

Correctness:

1. If $$k < \frac{9\cdot|V|}{10}$$, then note that $$t = 9\cdot |V| - 10k > 0$$, and so the output of the reduction $$G'$$ is well-defined. Now if $$G$$ has a clique $$C$$ of size at least $$k$$, then $$G'$$ has a clique of size at least $$k+t$$ (verify that $$C\cup \{ v: \text{v is a vertex in K_t}\}$$ is a clique of $$G'$$). Conversely, if $$G'$$ has a clique of $$C'$$ of size at least $$k + t$$, then the set $$C = C' \setminus \{ v: v \text{ is a vertex of K_t} \}$$ is a clique of $$G$$. Indeed, the reduction does not add new edges between the vertices of $$G$$. Also note that $$C$$ is of size $$|C| \geq |C'| - | \{ v: v \text{ is a vertex of K_t} \}| = |C'| - t \geq k+t - t = k$$ in $$G$$. All in all, we have that $$G$$ has a clique of size at least $$k$$ iff $$G'$$ has a clique of size at least $$k+t$$. Finally, note that $$\frac{k+t}{|G'|} = \frac{k+t}{|V|+t} = \frac{k + 9|V| - 10k}{|V| + 9|V| - 10k} = \frac{9|V| - 9k}{10|V|-10k} = \frac{9}{10}$$. So, $$G$$ has a clique of size at least $$k$$ iff $$G'$$ has a clique of size at least $$k+t = \frac{9}{10} |G'|$$.
2. If $$k \geq\frac{9\cdot|V|}{10}$$, then note that  $$10k - 9|V| \geq 0$$, and so the output of the reduction $$G'$$ is well-defined. For the first direction, if $$G$$ has a clique $$C$$ of size at least $$k$$, then $$G'$$ has a clique $$C'$$ of size at least $$9k$$. Indeed, we can take $$C' = \bigcup_{v\in C} c_9(v)$$, that is, $$C'$$ consists of the 9-cliques corresponding to the vertices in $$C$$ (verify that $$C'$$ is indeed a clique of size at least $$9k$$ in $$G'$$). The following holds $$\frac{|C'|}{|G'|} \geq \frac{9k}{|G'|} = \frac{9k}{9|V|+t} = \frac{9k}{9|V| +10k-9|V| } = \frac{9}{10}$$. So $$G'$$ has a clique of size at least $$\frac{9|G'|}{10}$$. Conversely, assume that $$G'$$ has a clique $$C'$$ of size at least $$\frac{9|G'|}{10} = \frac{9\cdot (9|V| + t)}{10} = \frac{9\cdot(9|V| + 10k - 9|V|)}{10} = \frac{9\cdot 10k}{10} = 9k$$. Clearly, none of the added isolated vertices are in $$C'$$, and thus $$C'$$ consists of vertices $$p$$ such that $$p\in c_9(v)$$ for some $$v\in V$$. In words, $$C'$$ consists of vertices $$p$$ such that $$p$$ belongs to one of the 9-cliques of $$G'$$. Note that there could be two vertices $$p_1, p_2\in C'$$ such that both $$p_1$$ and $$p_2$$ are in $$c_9(v)$$ for some $$v\in V$$ (that is, $$C'$$ can have vertices that correspond to the same 9-clique). Now consider the following set $$C =\{ v\in V: \text{ there is p\in C' such that p\in c_9(v)} \}$$. We claim that $$C$$ is a clique of size at least $$k$$ in $$G$$, and thus we're done. To begin with, $$|C|\geq k$$ because for every $$v\in C$$ there are at most 9 $$p$$'s such that $$p\in c_9(v)$$ and $$p\in C'$$, and those 9 $$p$$'s correspond only to the vertex $$v$$ in $$C$$. So in the worst case, $$C'$$ consists of whole 9-cliques and we replace every 9-clique $$c_9(v)$$ with $$v$$ to get the set $$C$$. So, as $$|C'|\geq 9k$$, then $$|C|\geq k$$. Now to show that $$C$$ is a clique in $$G$$, let $$v_1, v_2$$ be two vertices in $$C$$. We need to show that $$\{u, v \}\in E$$. By definition of $$C$$, there are $$p_1, p_2 \in C'$$ such that $$p_1\in c_9(v_1)$$ and $$p_2\in c_9(v_2)$$. Since $$C'$$ is a clique of $$G'$$, we know that $$\{p_1, p_2 \}$$ is an edge of $$G'$$, and by definition of $$G'$$ this can happen only when $$\{v_1, v_2 \} \in E$$ (indeed, vertices of different 9-cliques are connected in $$G'$$ when the vertices defining the 9-cliques are connected in G).

It depends on what other problems you already know to be NP-hard and whether you use Karp or Turing reductions.

• I am using Karp reductions. Regarding the number of NP-hard languages, I am sure that whatever language you use to solve this problem, I am most likely familiar with it.
– Kapa
Dec 7, 2020 at 16:48