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 V1V1 and V2V2 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 m2+n−14 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 m2+n−14+k4 edges, where k is the parameter.We obtain an algorithm for the problem of runtime 8k(kn)O(1)8k(kn)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′⩽kk′⩽k and |V(G′)|=O(k3)|V(G′)|=O(k3). 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(k5).