Electronic Proceedings Article @InProceedings Internet-Beitrag in Tagungsband, Workshop

 Show entries of: this year (2022) | last year (2021) | two years ago (2020) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Mnich, Matthias Philip, Geevarghese Saurabh, Saket Suchy, Ondrej dblp dblp dblp dblp Not MPG Author(s): Saurabh, Saket Suchy, Ondrej
 Editor(s): D'Souza, Deepak Kavitha, Telikepalli Radhakrishnan, Jaikumar dblp dblp dblp Not MPII Editor(s): D'Souza, Deepak Kavitha, Telikepalli Radhakrishnan, Jaikumar
 BibTeX cite key*: MnichPhilipSaurabhSuchy2012a

 Title, Conference
 Title*: Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzík Bound published.pdf (594.22 KB) Booktitle*: 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) Event Address*: Hyderabad, India URL of the conference: http://www.fsttcs.org Event Date*: (no longer used): URL for downloading the paper: http://drops.dagstuhl.de/opus/volltexte/2012/3877/ Event Start Date: 15 December 2012 Event End Date: 17 December 2012 Language: English Organization: Indian Association for Research in Computing Science (IARCS)

 Publisher
 Publisher's Name: Schloss Dagstuhl/ Leibniz-Zentrum für Informatik Publisher's URL: http://www.dagstuhl.de/ Address*: Dagstuhl Type:

 Vol, No, pp., Year
 Series: Leibniz International Proceedings in Informatics Volume: 18 Number: Month: December Pages: 412-423 Sequence Number: Year*: 2012 ISBN/ISSN: 978-3-939897-47-7 10.4230/LIPIcs.FSTTCS.2012.412

 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}(n-1)$ edges. The property of being bipartite is $\lambda$-extendible for $\lambda=1/2$, and thus the Poljak-Turz\'{i}k bound generalizes the well-known Edwards-Erd\H{o}s bound for \textsc{Max-Cut}. We define a variant, namely \emph{strong} $\lambda$-extendibility, to which the Poljak-Turz\'{i}k bound applies. For a strongly $\lambda$-extendible graph property $\Pi$, we define the parameterized \textsc{Above Poljak-Turz\'{\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}(n-1)+k$ edges? The parameter is $k$, the surplus over the number of edges guaranteed by the Poljak-Turz\'{i}k bound. We consider properties $\Pi$ for which the \textsc{Above Poljak-Turz\'{\i}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\'{\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{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). URL for the Abstract: Tags, Categories, Keywords: Parameterized Algorithms, Above-Guarantee Parameterization, Max-Cut HyperLinks / References / URLs: http://drops.dagstuhl.de/opus/volltexte/2012/3877/ Copyright Message: Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut 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 Max-Cut: lambda-Extendible Properties
Parameterized Above the {Poljak-Turz{\'i}k} Bound},
BOOKTITLE = {32nd International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
PUBLISHER = {Schloss Dagstuhl/ Leibniz-Zentrum für Informatik},
YEAR = {2012},
ORGANIZATION = {Indian Association for Research in Computing Science (IARCS)},
VOLUME = {18},
PAGES = {412--423},
SERIES = {Leibniz International Proceedings in Informatics},