Fig. 11

The approximation ratio of five for the greedy algorithm is tight. Matching edges are bold, dashed edges are in the approximate solution and solid edges are in the optimal solution. \(G^*\) is composed by the cliques \({C_1 = \{a,b,c,d,e,f\}}\), \({C_2=\{g,h\}}\), \({C_3 = \{i,j,k,l\}}\) and \(C_4 = \{m,n,o,p\}\). All edges have weight zero except ac and the edges of \(S_{opt}\). We suppose that \(\sigma _p = 3\) and \(\sigma _c=0\), and the greedy algorithm chooses “the wrong edge” ac first. Consequently, the solution \(S_A\) given by the greedy algorithm is of weight 1, whereas an optimal solution would be of weight 5