Algoritmos para o problema do k-plex máximo utilizando paralelismo de bits e coloração

Abstract

The maximum k-plex problem is a relaxation of the maximum clique problem (TRUKHANOV et al., 2013) and can be presented as follows: given an undirected graph G = (V;E), find S ⊆ V with a maximum cardinality such that ⩝v ⋴ S,| Γ(v) ⋂ S| ≥ |S| - k, where Γ(v) represents the set of adjacent vertices of v. Algorithms to find the maximum k-plex in a graph are used, for example, in social networks to analyze cohesive subgroups. Social cohesion is used to explain and develop sociological theories Balasundaram, Butenko e Hicks (2011). In this work, we modified the algorithm proposed by McClosky e Hicks (2012), called BasicPlex, by adding an upper bound procedure and a branching strategy based on a heuristically obtained coloring, using a data structure called bit vectors and using saturated vertex lists for the generation of candidate sets. We empirically compared the upper bound presented in this paper with IWCCH of McClosky e Hicks (2012). Computational tests were performed. We introduce the algorithm called BasicPlexBranching (BPB) that combines the techniques listed above. This algorithm was compared to the RDPlex, solution proposed by Trukhanov et al. (2013). DIMACS instances were used to perform the tests and BPB obtained best result in 26 instances, whereas RDPlex did best in 21 instances.