Crowston, Robert ;
Jones, Mark ;
Muciaccia, Gabriele ;
Philip, Geevarghese ;
Rai, Ashutosh ;
Saurabh, Saket
Polynomial Kernels for lambdaextendible Properties Parameterized Above the PoljakTurzik Bound
Abstract
Poljak and Turzik (Discrete Mathematics 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)(n1)/2 edges. The property of being bipartite is
lambdaextendible for lambda =1/2, and so the PoljakTurzik bound
generalizes the wellknown EdwardsErdos bound for Max Cut. Other examples of lambdaextendible properties include: being an acyclic oriented graph, a balanced signed graph, or a qcolorable graph for some q in N.
Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambdaextendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambdaextendible property Pi is fixedparameter tractable (FPT) when parameterized above the PoljakTurzik bounddoes there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1lambda)(n1)/2+k edges?subject to the condition that the problem is FPT on a certain simple class of graphs called almostforests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambdaextendible properties which satisfy the additional criterion.
In this paper we settle the kernelization complexity of nearly all problems parameterized above PoljakTurzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when lambda=1/2), without using the assumption that the problem is FPT on almostforests of cliques. Thus our results not only remove the technical condition of being FPT on almostforests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.
BibTeX  Entry
@InProceedings{crowston_et_al:LIPIcs:2013:4359,
author = {Robert Crowston and Mark Jones and Gabriele Muciaccia and Geevarghese Philip and Ashutosh Rai and Saket Saurabh},
title = {{Polynomial Kernels for lambdaextendible Properties Parameterized Above the PoljakTurzik Bound}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {4354},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897644},
ISSN = {18688969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4359},
URN = {urn:nbn:de:0030drops43599},
doi = {10.4230/LIPIcs.FSTTCS.2013.43},
annote = {Keywords: Kernelization, Lambda Extension, AboveGuarantee Parameterization, MaxCut}
}
2013
Keywords: 

Kernelization, Lambda Extension, AboveGuarantee Parameterization, MaxCut 
Seminar: 

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

Issue date: 

2013 
Date of publication: 

2013 