de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Beyond Max-cut: Lambda-extendible Properties Parameterized Above the Poljak-Turzík Bound

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons71823

Philip,  Geevarghese
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Mnich, M., Philip, G., Saurabh, S., & Suchy, O. (2012). Beyond Max-cut: Lambda-extendible Properties Parameterized Above the Poljak-Turzík Bound. In D. D'Souza, T. Kavitha, & J. Radhakrishnan (Eds.), IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (pp. 412-423). Wadern: Schloss Dagstuhl. doi:10.4230/LIPIcs.FSTTCS.2012.412.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-F755-7
Zusammenfassung
Poljak and Turzík (Discrete Math.\ 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<λ<1 and λ-extendible property \Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H\in\Pi with at least λ{}m+\frac1-λ}{2}(n-1) edges. The property of being bipartite is λ-extendible for λ=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erd\H{o}s bound for \textsc{Max-Cut}. We define a variant, namely \emph{strong} λ-extendibility, to which the Poljak-Turzík bound applies. For a strongly λ-extendible graph property \Pi, we define the parameterized \textsc{Above Poljak-Turzí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 λ{}m+\frac{1-λ}{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 \textsc{Above Poljak-Turzí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ík (\Pi)} is FPT for all 0<λ<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).