\textsc{Max-Cut} parameterized above the Edwards-Erdős bound

DOI10.1007/S00453-014-9870-ZzbMATH Open1328.68086arXiv1112.3506OpenAlexW2799037470MaRDI QIDQ494801FDOQ494801

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-ErdH{o}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 several 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.

Full work available at URL: https://arxiv.org/abs/1112.3506

Recommendations

• Max-Cut parameterized above the Edwards-Erdős bound
• Linear kernels and linear-time algorithms for finding large cuts
• Linear kernels and linear-time algorithms for finding large cuts
• Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
• \textsc{Max-Cut Above Spanning Tree} is fixed-parameter tractable

zbMATH Keywords

fixed-parameter tractabilityalgorithms and data structurescombinatorial boundsmaximum cuts

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Graph theory
• Reducibility among Combinatorial Problems
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• Parametrized complexity theory.
• Max-Cut parameterized above the Edwards-Erdős bound
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• On the complexity of \(k\)-SAT
• Parameterized graph separation problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Extremal Properties of Bipartite Subgraphs
• Distance-hereditary graphs
• On some extremal problems in graph theory
• Title not available (Why is that?)
• On the existence of subexponential parameterized algorithms
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Note on maximal bisection above tight lower bound
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Title not available (Why is that?)
• Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
• The size of the largest bipartite subgraphs
• SDP gaps and UGC-hardness for max-cut-gain
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Maximum balanced subgraph problem parameterized above lower bound
• Bisections above Tight Lower Bounds
• Approximation and intractability results for the maximum cut problem and its variants
• Title not available (Why is that?)

Cited In (15)

• Large Independent Sets in Triangle-Free Planar Graphs
• Complexity of maximum cut on interval graphs
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• An improved kernel for max-bisection above tight lower bound
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Linear kernels and linear-time algorithms for finding large cuts
• Max-Cut parameterized above the Edwards-Erdős bound
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• Perfect forests in graphs and their extensions
• Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
• Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
• Parameterized complexity of multi-node hubs
• New lower bound on Max Cut of hypergraphs with an application to \(r\)-Set Splitting

This page was built for publication: \textsc{Max-Cut} parameterized above the Edwards-Erdős bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494801)