# Discovering Locally Maximal Bipartite Subgraphs

arXiv: https://arxiv.org/abs/2211.10446 · HTML: https://mlsanity.com/paper/2211.10446/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 15 references that are in the map.
- First posted on arXiv 18 Nov 2022.

## Builds on (most cited first, 1 of 1)

- [Drawing Order Diagrams Through Two-Dimension Extension](https://mlsanity.com/paper/1906.06208/) (2019)

## Built on by (most cited first, 1 of 1)

- [Maximal Ordinal Two-Factorizations](https://mlsanity.com/paper/2304.03338/) (2023)

## Abstract (arXiv)

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