Beyond Max-Cut: λ-Extendible Properties Parameterized Above the Poljak-Turzík Bound

Poljak and Turzík (Discrete Mathematics 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 spanning subgraph \(H \in \Pi\) with at least \(\lambda m+(n-1)(1-\lambda)/2\) edges. The property of being bipartite is \(\lambda\)-extendible for \(\lambda=1/2\) and, thus, the Poljak-Turzík bound generalizes the well-known Edwards-Erdös bound for Max-Cut.

We define a variant, namely strong \(\lambda\)-extendibility, to which the Poljak-Turzík bound applies. For a strong \(\lambda\)-extendible graph property \(\Pi\), we define the parameterized 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 \(\lambda m+(n-1)(1-\lambda)/2 + 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 Above Poljak-Turzík(\(\Pi\)) problem is fixed-parameter tractable (\(\mathsf{FPT}\)) on graphs which are \(\mathcal{O}(k)\) vertices away from being a graph in which each block is a clique. We show that for all such properties, Above Poljak-Turzík(\(\Pi\)) is \(\mathsf{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ös bound, and yield \(\mathsf{FPT}\) algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is \(\mathsf{FPT}\); indeed we show, more generally, that the above-guarantee version of any problem defined by a homomorphism into a fixed vertex-transitive graph is \(\mathsf{FPT}\). Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem is \(\mathsf{FPT}\), thus solving an open question of Raman and Saurabh (Theoretical Computer Science 2006).

This is joint work with Matthias Mnich, Geevarghese Philip, and Saket Saurabh.

Recording