I am working with an undirected graph G where the maximum degree is bounded by a constant d. My goal is to check whether G contains a complete bipartite subgraph K_{i,j} as a subgraph, for small values of i, j (specifically, i, j < 8).

I currently use the following brute-force approach to detect a K_{i,j} subgraph:

nodes = [u for u in self.g if len(self.g[u]) >= j]
set_combinations = combinations(nodes, i)
for A in set_combinations:
  common_neighbors = set(self.g)
  for u in A:
    common_neighbors &= self.g[u]
    if len(common_neighbors) >= j:
      return False # K_ij found
  return True

This method works correctly but becomes slow as the graph size increases. The main bottleneck seems to be:

• Enumerating all subsets of i nodes (O(n^i) complexity).
• Intersecting neighbor sets iteratively, which can be costly for large graphs.

Given that the maximum degree is bounded and i, j are small, I wonder if there are more efficient approaches.