A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem. (May 2016)

• Record Type: Journal Article
• Authors: Marinelli, Fabrizio; Parente, Angelo
• Is Part Of: Computers & operations research. Volume 69(2016)
• Page Start: 68
• Page End: 78
• Publication Date: 2016-05
• Subjects: Network matrix -- Signed graph -- Independent set -- Maximum balanced induced subgraph -- Vertex frustration; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.12.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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 (thembis problem). In the present work, we propose a greedy approach for thembis 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. Abstract : Highlights: 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.