Finding Maximum Edge Bicliques in Tree Convex Graphs

Abstract

A bipartite graph is said to be tree convex if there exists a tree T defined over one part such that the neighborhood of every vertex in the other part forms a connected subtree of T. We study the problem of finding a maximum edge biclique—namely, a complete bipartite subgraph containing the largest possible number of edges—in tree convex bipartite graphs. For the special case of triad convex graphs, where T has exactly three leaves, we present an O(n² polylog n)-time algorithm, significantly improving the previous best O(n⁵)-time solution. More generally, for tree convex graphs where the underlying tree has a constant number d of leaves, we present an O(n^d-1 polylog n)-time algorithm, which improves the best previously known runtime by a factor of n³ / polylog n for any constant d ≥ 3.