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 协议之条款下提供，附加条款亦可能应用