Isolation concepts for efficiently enumerating dense subgraphs

In an undirected graph G = ( V, E ), a set of k vertices is called c -isolated if it has less than c ⋅ k 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 c -isolated maximal cliques in O ( 4 c ⋅ c 4 ⋅ | E | ) time. We extend this to enumerating all maximal c -isolated cliques (which are a superset) and improve the running time bound to O ( 2. 8 9 c ⋅ c 2 ⋅ | E | ), 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 s -plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s -plex is the parameter and a fixed-parameter algorithm for enumerating isolated s -plexes when the parameter describes the degree of isolation.

Authors

• Christian Komusiewicz Institute of Computer Science, Friedrich Schiller University Jena, Germany
• Falk Hüffner
• Hannes Moser
• Rolf Niedermeier

Keywords

• NP-hard problem
• Parameterized complexity
• Fixed-parameter tractability
• Exact algorithm
• Clique
• s -plex