Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 14, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Matthias Mnich (Universitaet des Saarlandes)
We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erdos bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size m/2 + (n−1)/4 + k in time 8k * O(n4), or decides that no such cut exists.
This answers a long-standing open question from parameterized complexity that has been posed a number of times over the past 15 years.
Our algorithm is asymptotically optimal, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.
This work appeared at ICALP 2012, and is joint with Robert Crowston and Mark Jones from Royal Holloway.
Automatic MiSe System Software Version 1.4803M | admin login