Item

Abstract

Poljak and Turzík (Discrete Math.\ 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<λ<1 and λ-extendible property \Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H\in\Pi with at least λ{}m+\frac1-λ}{2}(n-1) edges. The property of being bipartite is λ-extendible for λ=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erd\H{o}s bound for \textsc{Max-Cut}. We define a variant, namely \emph{strong} λ-extendibility, to which the Poljak-Turzík bound applies. For a strongly λ-extendible graph property \Pi, we define the parameterized \textsc{Above Poljak-Turzík (\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 λ{}m+\frac{1-λ}{2}(n-1)+k edges? The parameter is k, the surplus over the number of edges guaranteed by the Poljak-Turzík bound. We consider properties \Pi for which the \textsc{Above Poljak-Turzík (\Pi)} problem 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, \textsc{Above Poljak-Turzík (\Pi)} is FPT for all 0<λ<1. Our results hold for properties of oriented graphs and graphs with edge labels. Our results generalize the recent result of Crowston et al. (ICALP 2012) on \textsc{Max-Cut} parameterized above the Edwards-Erd\H{o}s bound, and yield \textsf{FPT} algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee \textsc{Max q-Colorable Subgraph} problem is \textsf{FPT}. Our results also imply that the parameterized above-guarantee \textsc{Oriented Max Acyclic Digraph} problem is \textsf{FPT, thus solving an open question of Raman and Saurabh (Theor.\ Comput.\ Sci.\ 2006).