Question

Let$MAX-CLIQUE=\left\{\right(G,k\left)\right|alargestcliqueinGisofsizeexactlyk\}$. Use the result of Problem 7.47 to show that MAX-CLIQUEis DP-complete.

Short answer

MAX-CLIQUEis DP-complete.

Step-by-step solution

To Prove the MAX-CLIQUE

To use the result of problem. It can be proven that MAX-CLIQUE is DP-Hard if a polynomial time reduction from C to MAX-CLIQUE exists.

To Generate the edge relations

Let a tuple $(G_1,k_1,G_2,k_2)$. In polynomial time, a pair (G,k) from the tuple is generated such that $(G_1,k_1,G_2,k_2)\in C$iff $\left(G,k\right)\in MAX-CLIQUE$.

Let $N_1,N_2$represent the node sets of $G_1 and G_2$and $E_1,E_2$their edge relations, respectively. Let's call $k_{k\text{'}}$be the size clique $k\text{'}$.

There can be no clique $G_1^{\text{'}}$larger than $k_1$, and there is a clique of size $k_1$if and only if $G_1$also has a clique of size $k_1$.

For $r\in N{}^{\text{'}}{\mathrm{G}}_1$is extended to a graph ${G_r}^1$by substituting an instance of $k_r$and then is an edge from each node.

The graph $G_1^r$consists clique of size $k_{1+r}$so $G_1$has a clique of size k_{1}, iff the maximum-sized clique in $G_1^r$has size $k_{1+r}$.

There exits a case that $G_2^r$consists $k_2+r$clique if $G_2$has a $k_2$-clique. Also $G_2$consists $k_2+r-1$sized clique and consists no clique larger than $k_2+r$.

If $k_1>k_2$then $G\text{'}=G_1^0\times G_2^{k_1-k_2}$else .

Thus, MAX-CLIQUEis DP-complete.