Using shortcut edges to maximize the number of triangles in graphs

In this paper, we consider the following problem: given an undirected graph G=(V,E)G=(V,E) and an integer kk, find I⊆V2I⊆V2 with |I|≤k|I|≤k in such a way that G′=(V,E∪I)G′=(V,E∪I) has the maximum number of triangles (a cycle of length 33). We first prove that this problem is NP-hard and then give an approximation algorithm for it.