  Poljak and Turz\'ik (Discrete Math. 1986) introduced the notion of
\lambda-extendible properties of graphs as a generalization of the property of
being bipartite. They showed that for any 0<\lambda<1 and \lambda-extendible
property \Pi, any connected graph G on n vertices and m edges contains a
subgraph H \in {\Pi} with at least \lambda m+ (1-\lambda)/2 (n-1) edges. The
property of being bipartite is 1/2-extendible, and thus this bound generalizes
the Edwards-Erd\H{o}s bound for Max-Cut.
  We define a variant, namely strong \lambda-extendibility, to which the bound
applies. For a strongly \lambda-extendible graph property \Pi, we define the
parameterized Above Poljak- Turz\'ik (APT) (\Pi) problem as follows: Given a
connected graph G on n vertices and m edges and an integer parameter k, does
there exist a spanning subgraph H of G such that H \in {\Pi} and H has at least
\lambda m + (1-\lambda)/2 (n - 1) + k edges? The parameter is k, the surplus
over the number of edges guaranteed by the Poljak-Turz\'ik bound.
  We consider properties {\Pi} for which APT (\Pi) is fixed- parameter
tractable (FPT) on graphs which are O(k) vertices away from being a graph in
which each block is a clique. We show that for all such properties, APT (\Pi)
is FPT for all 0<\lambda<1. Our results hold for properties of oriented graphs
and graphs with edge labels. Our results generalize the result of Crowston et
al. (ICALP 2012) on Max-Cut parameterized above the Edwards-Erd\H{o}s bound,
and yield FPT algorithms for several graph problems parameterized above lower
bounds, e.g., Max q-Colorable Subgraph problem. Our results also imply that the
parameterized above-guarantee Oriented Max Acyclic Digraph problem is FPT, thus
solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).
