This paper discusses the maximal biclique enumeration problem in bipartite graphs, its applications, and the current theoretical bounds. It proposes research directions to potentially improve the worst-case time complexity and provides a detailed analysis under standard complexity assumptions.
Key findings
The current best-known bound for maximal biclique enumeration is α≈1.3954, derived from a partition-based branch-and-bound algorithm.
The paper identifies three promising research directions: refined pivot selection, extension of optimally-solvable subgraphs, and conditional lower bounds based on the Exponential Time Hypothesis.
Any improvement to the branching factor below 1.35 would require fundamentally new techniques under standard complexity assumptions.
Limitations & open questions
The paper does not provide empirical results to validate the theoretical proposals.
The research directions proposed are speculative and require further exploration and validation.