Electronic Proceedings Article
@InProceedings
InternetBeitrag in Tagungsband, Workshop  
BibTeX cite key*: 
MnichPhilipSaurabhSuchy2012a 

URL for Reference: 

Note: 

(LaTeX) Abstract: 
Poljak and Turz{\'{i}}k (Discrete Math.\ 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+\frac{1\lambda}{2}(n1)$ edges. The
property of being bipartite is $\lambda$extendible for $\lambda=1/2$, and
thus the PoljakTurz\'{i}k bound generalizes the wellknown
EdwardsErd\H{o}s bound for \textsc{MaxCut}.
We define a variant, namely \emph{strong}
$\lambda$extendibility, to which the PoljakTurz\'{i}k bound applies. For a
strongly $\lambda$extendible graph property $\Pi$, we define the parameterized
\textsc{Above PoljakTurz\'{\i}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+\frac{1\lambda}{2}(n1)+k$
edges? The parameter is $k$, the surplus over the number of
edges guaranteed by the PoljakTurz\'{i}k bound.
We consider properties $\Pi$ for which the \textsc{Above PoljakTurz\'{\i}k ($\Pi$)} 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, \textsc{Above PoljakTurz\'{\i}k ($\Pi$)} 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 \textsc{MaxCut} parameterized above the
EdwardsErd\H{o}s bound, and yield \textsf{FPT} algorithms for several graph
problems parameterized above lower bounds. For instance, we get
that the aboveguarantee \textsc{Max $q$Colorable Subgraph} problem is \textsf{FPT}. Our results
also imply that the parameterized aboveguarantee \textsc{Oriented Max Acyclic Digraph}
problem
is \textsf{FPT}, thus solving an open question of Raman and Saurabh
(Theor.\ Comput.\ Sci.\ 2006). 
URL for the Abstract: 



Tags, Categories, Keywords: 
Parameterized Algorithms, AboveGuarantee Parameterization, MaxCut 
HyperLinks / References / URLs: 
http://drops.dagstuhl.de/opus/volltexte/2012/3877/ 
Copyright Message: 

Personal Comments: 

Download
Access Level: 
Public 

MPG Unit:  MaxPlanckInstitut für Informatik 
 
MPG Subunit:  Algorithms and Complexity Group 
Appearance:  MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort 
BibTeX Entry:
@INPROCEEDINGS{MnichPhilipSaurabhSuchy2012a,
AUTHOR = {Mnich, Matthias and Philip, Geevarghese and Saurabh, Saket and Suchy, Ondrej},
EDITOR = {D'Souza, Deepak and Kavitha, Telikepalli and Radhakrishnan, Jaikumar},
TITLE = {Beyond MaxCut: lambdaExtendible Properties
Parameterized Above the {PoljakTurz{\'i}k} Bound},
BOOKTITLE = {32nd International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
PUBLISHER = {Schloss Dagstuhl/ LeibnizZentrum für Informatik},
YEAR = {2012},
ORGANIZATION = {Indian Association for Research in Computing Science (IARCS)},
VOLUME = {18},
PAGES = {412423},
SERIES = {Leibniz International Proceedings in Informatics},
ADDRESS = {Hyderabad, India},
MONTH = {December},
ISBN = {9783939897477},
DOI = {10.4230/LIPIcs.FSTTCS.2012.412},
}
Entry last modified by Anja Becker, 07/08/2014
Edit History (please click the blue arrow to see the details)
 Editor(s)
[Library]  Created
12/18/2012 05:50:58 AM 
Revisions
4.
3.
2.
1.
0.  Editor(s)
Anja Becker
Anja Becker
Uwe Brahm
Geevarghese Philip
Geevarghese Philip  Edit Dates
13.03.2013 13:17:47
08.02.2013 12:02:33
01022013 03:10:41 PM
12/19/2012 10:49:16 AM
12/18/2012 05:50:59 AM 