This paper proposes clique relaxations to identify clusters in biological networks. In particular, the maximum $n$-clique and maximum $n$-club problems on an arbitrary graph are introduced and their recognition versions are shown to be NP-complete. In addition, integer programming formulations are proposed and the results of sample numerical experiments performed on biological networks are reported.
At the time we wrote and published this paper, we were unfortunately not aware of publications [1,2] that pre-date us on this topic. In particular, reference [1] proves the NP-hardness of the problem, which makes our result in Theorem 1 unnecessary. In fact, our reduction is essentially the same although we arrived at it from a different perspective, as made evident by our presentation. We have rectified this oversight in all our subsequent publications on this topic by appropriately citing and crediting the works of Bourjolly, Laporte, and Pesant. Theorem 2 in our paper is still relevant as it applies to k-clubs in graphs of fixed diameter, e.g., graphs of diameter k+1, a stronger observation.
Frustratingly, the proof of Theorem 1 in our paper is not only redundant, it is also incorrect/incomplete. The proof provided works for odd values of the parameter, just like in Theorem 2. It does not work for even values of the parameter (again, just like in Theorem 2). The reduction provided in Theorem 2 for even values of the parameter should have been used in Theorem 1 as well. We are grateful to Sepp Hartung for bringing this error to our attention.
Although very unlikely, I apologize if these errors caused any issues for you in your research! –B.B.