Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Beyond Max-cut: Lambda-extendible Properties Parameterized Above the Poljak-Turzík Bound

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.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-F755-7 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-AD16-8
Genre: Konferenzbeitrag
Latex : Beyond Max-cut: $\lambda$-extendible Properties Parameterized Above the {Poljak-Turz\'ik} Bound

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
http://drops.dagstuhl.de/opus/volltexte/2012/3877/ (beliebiger Volltext)
Beschreibung:
-
OA-Status:

Urheber

einblenden:
ausblenden:
 Urheber:
Mnich, Matthias1, Autor
Philip, Geevarghese2, Autor           
Saurabh, Saket3, Autor
Suchy, Ondrej3, Autor
Affiliations:
1Cluster of Excellence Multimodal Computing and Interaction, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
3External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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).

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2012-12-10
 Publikationsstatus: Online veröffentlicht
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Anderer: Local-ID: 4C146804F0CD924CC1257AD8001AA3B8-MnichPhilipSaurabhSuchy2012a
DOI: 10.4230/LIPIcs.FSTTCS.2012.412
URN: urn:nbn:de:0030-drops-38776
BibTex Citekey: MnichPhilipSaurabhSuchy2012a
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science
Veranstaltungsort: Hyderabad, India
Start-/Enddatum: 2012-12-15 - 2012-12-17

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
  Kurztitel : FSTTCS 2012
Genre der Quelle: Konferenzband
 Urheber:
D'Souza, Deepak1, Herausgeber
Kavitha, Telikepalli1, Herausgeber
Radhakrishnan, Jaikumar1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Wadern : Schloss Dagstuhl
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 412 - 423 Identifikator: ISBN: 978-3-939897-47-7

Quelle 2

einblenden:
ausblenden:
Titel: Leibniz International Proceedings in Informatics
  Kurztitel : LIPIcs
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 18 Artikelnummer: - Start- / Endseite: - Identifikator: -