# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Beyond Max-cut: Lambda-extendible Properties Parameterized Above the Poljak-Turzík Bound

##### Locator

http://drops.dagstuhl.de/opus/volltexte/2012/3877/

(Any fulltext)

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mnich, M., Philip, G., Saurabh, S., & Suchy, O. (2012). Beyond Max-cut: Lambda-extendible
Properties Parameterized Above the Poljak-Turzík Bound. In D. D'Souza, T. Kavitha, & J. Radhakrishnan (*IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science*
(pp. 412-423). Wadern: Schloss Dagstuhl. doi:10.4230/LIPIcs.FSTTCS.2012.412.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-F755-7

##### 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).