\textsc{Max-Cut} parameterized above the Edwards-Erdős bound
From MaRDI portal
Publication:494801
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.
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
Cites work
- scientific article; zbMATH DE number 3510345 (Why is no real title available?)
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- scientific article; zbMATH DE number 780784 (Why is no real title available?)
- scientific article; zbMATH DE number 3307332 (Why is no real title available?)
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- Approximation and intractability results for the maximum cut problem and its variants
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Bisections above Tight Lower Bounds
- Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound
- Distance-hereditary graphs
- Graph theory
- Linear-Time Approximation Algorithms for the Max Cut Problem
- Max-Cut parameterized above the Edwards-Erdős bound
- Maximum balanced subgraph problem parameterized above lower bound
- Note on maximal bisection above tight lower bound
- On problems without polynomial kernels
- On some extremal problems in graph theory
- On the complexity of \(k\)-SAT
- On the existence of subexponential parameterized algorithms
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Parameterized graph separation problems
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Parametrized complexity theory.
- Reducibility among combinatorial problems
- SDP gaps and UGC-hardness for max-cut-gain
- Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
- Some Extremal Properties of Bipartite Subgraphs
- The size of the largest bipartite subgraphs
Cited in
(20)- Complexity of maximum cut on interval graphs
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- Balanced judicious bipartition is fixed-parameter tractable
- Max-Cut parameterized above the Edwards-Erdős bound
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- \textsc{Max-Cut Above Spanning Tree} is fixed-parameter tractable
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterized complexity of multi-node hubs
- Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
- \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel
- An improved kernel for max-bisection above tight lower bound
- Linear kernels and linear-time algorithms for finding large cuts
- Linear kernels and linear-time algorithms for finding large cuts
- Maximum cut parameterized by crossing number
- \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- New lower bound on Max Cut of hypergraphs with an application to \(r\)-Set Splitting
- Large independent sets in triangle-free planar graphs
- Perfect forests in graphs and their extensions
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
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)
