Options
Max-Cut parameterized above the Edwards-Erdős bound
Publikationstyp
Journal Article
Date Issued
2015-07-12
Sprache
English
Author(s)
TORE-URI
Journal
Volume
72
Issue
3
Start Page
734
End Page
757
Citation
Algorithmica (2015)
Publisher DOI
ArXiv ID
Publisher
Springer Nature
We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut parameterized above the Edwards-Erdős 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 2 O(k) ⋅n 4 , 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 has asymptotically optimal running time, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.
DDC Class
000: Allgemeines, Wissenschaft