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:
Given that the maximum degree is bounded and i, j are small, I wonder if there are more efficient approaches.
I incorporated an idea from the comments. I’m iterating through the nodes and, for each node, only consider its neighbors to construct the subgraph K_ij. This reduces the complexity of generating all possible combinations, but it’s still exponential for graphs with a high degree.
def is_k_ij_free(self, i: int, j: int) -> bool:
if i < 1 or j < 1:
raise ValueError("i and j must be greater than 0")
if i < j:
# swap i and j for better runtime
i, j = j, i
nodes = {u for u in self.g if len(self.g[u]) >= j}
for node in nodes:
neighbor_i = {u for u in self.g[node] if len(self.g[u]) >= i}
for A in combinations(neighbor_i, j):
common_neighbors = set(self.g)
for a in A:
common_neighbors &= self.g[a]
if len(common_neighbors) >= i:
return False
return True
Feel free to further improve it, or point out any errors I have overseen.