Exact Algorithms And Applications For Maximum Relaxation Clique Problems

A clique is a graph with an edge between any pair of vertices.In social networks,a clique can represent a closely connected community group.Therefore,it is of great practical significance to find a largest clique in networks and it also has become a clas-sic problem in social computing and data mining.Meanwhile,researchers realized that clique is overly restrictive in many applications.In a bid to better characterize the co-hesive subgroups in networks,various relaxed clique models are proposed.The relaxed clique models are often obtained by relaxing some constraints of clique.For example,k-core and k-plex relax the vertex degree constraint;k-clique and k-club relax the routing length constratint and k-block and k-bundle relax the connectivity constraint,where k is the intrinsic parameter of these models.The maximum relaxed clique problem,generalization of the well-known Maximum Clique Problem,aims to find a relaxed clique with the maximum cardinality in a given graph.In this paper,we study three problems related to the maximum relaxed clique problem.The first is the Maximum k-Plex Problem,the second is the Maximum k-Bundle Problem,and the third is the Minimum Sum Coloring Problem.We first study the Maximum k-Plex Problem and propose an exact algorithm based on the branch-and-bound technique.The upper bound of the theoretical running time of our algorithm is also given.It is the first algorithm that breaks the theoretical bound of 2~n where n is the number of vertices in the graph.Experimental results also show that our algorithm performs better than previous algorithms in the benchmark sets.For the second part,we study the connectivity relaxed model k-bundle.To solve the Maximum k-Bundle Problem,we first analysis the structural similarities and differences between k-plex and k-bundle and then design the branching rules extended from the exact algorithm for Maximum k-Plex.Meanwhile,more reduction rules based on the diameter and graph coloring are also given.Experiments validate the advantage of our algorithm,especially on large real-life social networks.At last,we give an application of the maximum relaxed clique problem to Minimum Sum Coloring.Minimum Sum Coloring is a well-studied problem in VLSI design and resource allocation fields.We give a method to construct the theoretical lower bounds of Minimum Sum Coloring using the maximum clique and maximum relaxed clique.