Mnich, Matthias ;
Philip, Geevarghese ;
Saurabh, Saket ;
Suchy, Ondrej
Beyond MaxCut: lambdaExtendible Properties Parameterized Above the PoljakTurzik Bound
Abstract
Poljak and Turzík (Discrete Math. 1986) introduced the notion of lambdaextendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < lambda < 1 and lambdaextendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda m+ (1lambda)/2 (n1) edges. The property of being bipartite is lambdaextendible for lambda=1/2, and thus the PoljakTurzík bound generalizes the wellknown EdwardsErdos bound for MAXCUT.
We define a variant, namely strong lambdaextendibility, to which the PoljakTurzík bound applies. For a strong lambdaextendible graph property \Pi, we define the parameterized Above PoljakTurzík 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+ (1lambda)/2 (n1)+k edges? The parameter is k, the surplus over the number of edges guaranteed by the PoljakTurzík bound.
We consider properties Pi for which the Above PoljakTurzík problem is fixedparameter 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, Above PoljakTurzík is FPT for all 0< lambda <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 MAXCUT parameterized above the EdwardsErdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the aboveguarantee Max qColorable Subgraph problem is FPT. Our results also imply that the parameterized aboveguarantee Oriented Max Acyclic Digraph problem thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).
BibTeX  Entry
@InProceedings{mnich_et_al:LIPIcs:2012:3877,
author = {Matthias Mnich and Geevarghese Philip and Saket Saurabh and Ondrej Suchy},
title = {{Beyond MaxCut: lambdaExtendible Properties Parameterized Above the PoljakTurzik Bound}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {412423},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3877},
URN = {urn:nbn:de:0030drops38776},
doi = {10.4230/LIPIcs.FSTTCS.2012.412},
annote = {Keywords: Algorithms and data structures; fixedparameter algorithms; bipartite graphs; aboveguarantee parameterization}
}
2012
Keywords: 

Algorithms and data structures; fixedparameter algorithms; bipartite graphs; aboveguarantee parameterization 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Issue date: 

2012 
Date of publication: 

2012 