Separator-based data reduction for signed graph balancing

Separator-based data reduction for signed graph balancing

0.00 Avg rating0 Votes
Article ID: iaor20107596
Volume: 20
Issue: 4
Start Page Number: 335
End Page Number: 360
Publication Date: Nov 2010
Journal: Journal of Combinatorial Optimization
Authors: , ,
Abstract:

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.

Reviews

Required fields are marked *. Your email address will not be published.