License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.43
URN: urn:nbn:de:0030-drops-43599
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4359/
Crowston, Robert ;
Jones, Mark ;
Muciaccia, Gabriele ;
Philip, Geevarghese ;
Rai, Ashutosh ;
Saurabh, Saket
Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound
Abstract
Poljak and Turzik (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+(1-lambda)(n-1)/2 edges. The property of being bipartite is
lambda-extendible for lambda =1/2, and so the Poljak-Turzik bound
generalizes the well-known Edwards-Erdos bound for Max Cut. Other examples of lambda-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some q in N.
Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambda-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambda-extendible property Pi is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound---does there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1-lambda)(n-1)/2+k edges?---subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambda-extendible properties which satisfy the additional criterion.
In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik 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 almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests 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 lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {43--54},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4359},
URN = {urn:nbn:de:0030-drops-43599},
doi = {10.4230/LIPIcs.FSTTCS.2013.43},
annote = {Keywords: Kernelization, Lambda Extension, Above-Guarantee Parameterization, MaxCut}
}
|
Keywords: |
|
Kernelization, Lambda Extension, Above-Guarantee Parameterization, MaxCut |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) |
|
Issue Date: |
|
2013 |
|
Date of publication: |
|
10.12.2013 |
