Discovering Locally Maximal Bipartite Subgraphs
This work addresses a graph analysis problem for researchers and practitioners dealing with large graphs, but it is incremental as it focuses on a weaker variant of an existing hard problem.
The paper tackles the computationally hard problem of finding maximal bipartite subgraphs in large graphs by proposing a weaker notion of locally maximal bipartite subgraphs and developing three heuristic approaches (greedy, simulated annealing, genetic algorithm) to extract them, comparing their performance in terms of time and vertex cardinality against a SAT-solver-based global solution on benchmark datasets.
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. For this, we present three heuristic approaches to extract such subgraphs and compare their results to the solutions of the global problem. For the latter, we employ the algorithmic strength of fast SAT-solvers. Our three proposed heuristics are based on a greedy strategy, a simulated annealing approach, and a genetic algorithm, respectively. We evaluate all four algorithms with respect to their time requirement and the vertex cardinality of the discovered bipartite subgraphs on several benchmark datasets