Maximum balanced subgraph problem parameterized above lower bound ?
We consider graphs without loops or parallel edges in which every edge is assigned + or ?. Such a signed graph is balanced if its vertex set can be partitioned into parts V1 V 1 and V2 V 2 such that all edges between vertices in the same part have sign + and all edges between vertices of different parts have sign ? (one of the parts may be empty). It is well-known that every connected signed graph with n vertices and m  edges has a balanced subgraph with at least m 2 + n ? 1 4 edges and this bound is tight. We consider the following parameterized problem: given a connected signed graph G with n vertices and m edges, decide whether G  has a balanced subgraph with at least m 2 + n ? 1 4 + k 4 edges, where k is the parameter. We obtain an algorithm for the problem of runtime 8k(kn)O(1) 8 k ( k n ) O ( 1 ) . We also prove that for each instance (G,k) ( G , k ) of the problem, in polynomial time, we can either solve (G,k) ( G , k ) or produce an equivalent instance (G?,k?) ( G ? , k ? ) such that k??k k ? ? k and |V(G?)|=O(k3) | V ( G ? ) | = O ( k 3 ) . Our first result generalizes a result of Crowston, Jones and Mnich (ICALP 2012) on the corresponding parameterization of Max Cut (when every edge of G  has sign ?). Our second result generalizes and significantly improves the corresponding result of Crowston, Jones and Mnich for MaxCut: they showed that |V(G?)|=O(k5) | V ( G ? ) | = O ( k 5 ) .
balanced subgraph signed graph fixed parameter tractable kernel