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

A signed graph, i.e., an undirected graph whose edges have labels in {-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