A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem

• We develop the heuristic for the maximum balanced induced subgraph problem.
• NCCH is based on a graph transformation rule that shortens negative cycles.
• NCCH largely outperforms the best heuristic to date.
• NCCH generalizes the Minimum-Degree Greedy algorithm for the maximum independent set problem.

A signed graph, i.e., an undirected graph whose edges have labels in {−1,+1}{−1,+1}, is balanced if it has no negative cycles. Given a signed graph, we are interested in a balanced induced subgraph of maximum order (the mbis problem). In the present work, we propose a greedy approach for the mbis problem that is based on the progressive shortening of negative cycles, and that generalizes the well-known minimum-degree greedy heuristic for the maximum independent set problem. An extensive computational study on three classes of instances shows that the new algorithm outperforms the reference heuristics proposed in the literature.