Isolation concepts for efficiently enumerating dense subgraphs

Abstract: In an undirected graph , a set of  vertices is called -isolated if it has less than  outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all -isolated maximal cliques in  time. We extend this to enumerating all maximal -isolated cliques (which are a superset) and improve the running time bound to , using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to -plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the -plex is the parameter and a fixed-parameter algorithm for enumerating isolated -plexes when the parameter describes the degree of isolation. [Copyright &y& Elsevier]