\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
- 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: -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
- 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?)
- 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
(24)- Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
- \textsc{Max-Cut Above Spanning Tree} is fixed-parameter tractable
- \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
- An improved kernel for max-bisection above tight lower bound
- Parameterized complexity of multi-node hubs
- 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}
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel
- Max-Cut parameterized above the Edwards-Erdős bound
- New lower bound on Max Cut of hypergraphs with an application to r-Set Splitting
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Linear kernels and linear-time algorithms for finding large cuts
- Maximum cut parameterized by crossing number
- Balanced judicious bipartition is fixed-parameter tractable
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- Large independent sets in triangle-free planar graphs
- Perfect forests in graphs and their extensions
- Complexity of maximum cut on interval graphs
- An FPT algorithm for splitting a necklace among two thieves
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- An FPT algorithm for splitting a necklace among two thieves
- Linear kernels and linear-time algorithms for finding large cuts
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
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)
