Separator-based data reduction for signed graph balancing |
| |
Authors: | Falk Hüffner Nadja Betzler Rolf Niedermeier |
| |
Affiliation: | 1.Institut für Informatik,Friedrich-Schiller-Universit?t Jena,Jena,Germany |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|