0
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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).
$\endgroup$
0
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Kapa
    Dec 7, 2020 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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