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) >= j] set_combinations = combinations(nodes, i) for A in set_combinations: common_neighbors = set(self.g) for u in A: common_neighbors &= self.g 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. Continue reading...
