35-2 Approximating the size of a maximum clique

Let $G=(V,E)$ be an undirected graph. For any $k\ge 1$, define $G^{(k)}$ to be the undirected graph $(V^{(k)},E^{(k)})$, where $V^{(k)}$ is the set of all ordered $k$-tuples of vertices from $V$ and $E^{(k)}$ is defined so that $(v_1,v_2,\dots ,v_k)$ is adjacent to $(w_1,w_2,\dots ,w_k)$ if and only if for $i=1,2,\dots ,k$, either vertex $v_i$ is adjacent to $w_i$ in $G$, or else $v_i=w_i$.

a. Prove that the size of the maximum clique in $G^{(k)}$ is equal to the $k$th power of the size of the maximum clique in $G$.

b. Argue that if there is an approximation algorithm that has a constant approximation ratio for finding a maximum-size clique, then there is a polynomial-time approximation scheme for the problem.

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用