Algoritmo exato para o problema do k-plex máximo

Abstract

The k-plex maximum problem can be presented as: Given an undirected graph G = (V,E), find S ⊆V with the highest cardinality such that ∀v ∈ S,|Γ(v)∩S| ≥ |S|−k, where Γ(v) represents the set of vertices adjacent to v (SILVA; TAVARES, 2016), ie, each vertex is non-adjacent to at most k vertices. The problem of the maximum k-plex is a maximum clique relaxation (TRUKHANOV et al., 2013). Every clique is a 1-plex. Algorithms to find the k-plex maximum have as one of its applications the analysis of cohesive groups in social networks. n this paper, we have assembled the techniques presented by Silva e Tavares (2016) and McClosky e Hicks (2012) to create a new algorithm for the maximal k-plex problem. This algorithm uses the branch-and-bound technique and adds an upper bound using the co-k-coloration technique proposed by McClosky e Hicks (2012). Computational tests were made with the purpose of comparing the efficiency between the algorithm proposed by this work and the algorithm of Silva e Tavares (2016). DIMACS inputs and randomly generated instances were used and the algorithm proposed by this work performed best in 40 of 75 instances.