Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}

DOI10.1007/S00224-018-09909-5MaRDI QIDQ2300620zbMATH OpenOpenAlexFDO

Authors Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi

Publication date 27 February 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-018-09909-5

zbMATH Keywords

above guarantee parameterizationfixed-parameter tractable algorithmmax-cutpolynomial kernel

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• \textsc{Max-Cut Above Spanning Tree} is fixed-parameter tractable
• Max-Cut parameterized above the Edwards-Erdős bound
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel

Cites work

• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• scientific article; zbMATH DE number 3510345 (Why is no real title available?)
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• Linear kernels and linear-time algorithms for finding large cuts
• Max-Cut parameterized above the Edwards-Erdős bound
• On some extremal problems in graph theory
• On the existence of subexponential parameterized algorithms
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Reducibility among combinatorial problems
• Some Extremal Properties of Bipartite Subgraphs

Cited in

(11)

• \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
• \((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
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• 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
• Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound

This page was built for publication: Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}

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