Enumeration of isolated cliques and pseudo-cliques

Abstract

In this article, we consider isolated cliques and isolated dense subgraphs. For a given graph G , a vertex subset S of size k (and also its induced subgraph G ( S )) is said to be c -isolated if G ( S ) is connected to its outside via less than ck edges. The number c is sometimes called the isolation factor . The subgraph appears more isolated if the isolation factor is smaller. The main result in this work shows that for a fixed constant c , we can enumerate all c -isolated maximal cliques (including a maximum one, if any) in linear time. In more detail, we show that, for a given graph G of n vertices and m edges, and a positive real number c , all c -isolated maximal cliques can be enumerated in time O ( c 4 2 2c m ). From this, we can see that: (1) if c is a constant, all c -isolated maximal cliques can be enumerated in linear time, and (2) if c = O (log n ), all c -isolated maximal cliques can be enumerated in polynomial time. Moreover, we show that these bounds are tight. That is, if f ( n ) is an increasing function not bounded by any constant, then there is a graph of n vertices and m edges for which the number of f ( n )-isolated maximal cliques is superlinear in n + m . Furthermore, if f ( n ) = ω(log n ), there is a graph of n vertices and m edges for which the number of f ( n )-isolated maximal cliques is superpolynomial in n + m . We next introduce the idea of pseudo-cliques. A pseudo-clique having an average degree α and a minimum degree β, denoted by PC (α,β), is a set V ′ ⊆ V such that the subgraph induced by V ′ has an average degree of at least α and a minimum degree of at least β. This article investigates these, and obtains some cases that can be solved in polynomial time and some other cases that have a superpolynomial number of solutions. Especially, we show the following results, where k is the number of vertices of the isolated pseudo-cliques: (1) For any ϵ > 0 there is a graph of n vertices for which the number of 1-isolated PC ( k - (log k ) 1 + ϵ , k /(log k ) 1 + ϵ ) is superpolynomial, and (2) there is a polynomial-time algorithm which enumerates all c -isolated PC ( k - log k , k /log k ), for any constant c .