Discovering Locally Maximal Bipartite Subgraphs

Understand

Induced bipartite subgraphs of maximal vertex cardinality are an essential concept for the analysis of graphs.

• Yet, discovering them in large graphs is known to be computationally hard.
• Therefore, we consider in this work a weaker notion of this problem, where we discard the maximality constraint in favor of inclusion maximality.
• Thus, we aim to discover locally maximal bipartite subgraphs.