Edge addition
We use a reduction to the Minimum Vertex Cover problem to find all minimal sets of up to k edges that eliminate all the squares in the graph.
Each eliminating set of edges, S = {e1,..., er}, is assigned a cost:
where sim(ei) takes values between 1.0 and 0.0, and measures our confidence in adding ei to the graph. Since the addition of ei = (ui, vi) implies an interaction or functional equivalence between proteins ui and vi, we chose sim(ei) to be the amount of overlap between the neighborhoods of ui and vi, i.e., sim(ei) = , where  (vi) denotes a set of neighbors of node vi in the graph. Intuitively, sim(ei) measures how close ui and vi are to being a pair of weak siblings. If ui and vi have the same neighborhoods then sim(ei) = 1.0; as the overlap between the neighborhoods decreases, sim(ei) goes to 0.0. Then, we pick an edge set with the minimum cost from all the edge sets that do not form a P4, which is entirely contained in one of the maximal cliques of the modified graph. The last requirement is necessary to ensure that each functional group is a cograph.