License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.412
URN: urn:nbn:de:0030-drops-38776
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3877/
Mnich, Matthias ;
Philip, Geevarghese ;
Saurabh, Saket ;
Suchy, Ondrej
Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
Abstract
Poljak and Turzí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+ (1-lambda)/2 (n-1) edges. The property of being bipartite is lambda-extendible for lambda=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erdos bound for MAXCUT.
We define a variant, namely strong lambda-extendibility, to which the Poljak-Turzík bound applies. For a strong lambda-extendible graph property \Pi, we define the parameterized Above Poljak-Turzí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+ (1-lambda)/2 (n-1)+k edges? The parameter is k, the surplus over the number of edges guaranteed by the Poljak-Turzík bound.
We consider properties Pi for which the Above Poljak-Turzík 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, Above Poljak-Turzí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 Edwards-Erdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is FPT. Our results also imply that the parameterized above-guarantee 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 Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {412--423},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-47-7},
ISSN = {1868-8969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2012/3877},
URN = {urn:nbn:de:0030-drops-38776},
doi = {10.4230/LIPIcs.FSTTCS.2012.412},
annote = {Keywords: Algorithms and data structures; fixed-parameter algorithms; bipartite graphs; above-guarantee parameterization}
}
|
Keywords: |
|
Algorithms and data structures; fixed-parameter algorithms; bipartite graphs; above-guarantee parameterization |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
14.12.2012 |
