Exact algorithms for problems related to the densest k-set problem

Many graph concepts such as cliques, k-clubs, and k-plexes are used to define cohesive subgroups in a social network. The concept of densest k-set is one of them. A densest k-set in an undirected graph G = (V, E) is a vertex set S subset of V of size k such that the number of edges in the subgraph of G induced by S is maximum among all subgraphs of G induced by vertex sets of size k. One can obtain a densest k-set of G in O (k(2)n(k)) time by exhaustive-search technique for an undirected graph of n vertices and a number k < n. However, if the value of k approaches n/2, the running time of the exhaustive-search algorithm is O*(2(n)). Whether there exists an O*(c(n))-time algorithm with the fixed constant c < 2 to find a densest k-set in an undirected graph of n vertices remains open in the literature. In this paper, we point out that the densest k-set problem and a class of problems related to the concept of densest k-sets can be solved in time O*(1.7315(n)). (C) 2014 Elsevier B.V. All rights reserved.