Polynomial-time approximation scheme for minimum k-cut in planar and minor-free graphs

DOI10.1137/1.9781611975482.65MaRDI QIDQ5236249zbMATH OpenOpenAlexFDO

Authors MohammadHossein Bateni, Alireza Farhadi, Mohammad T. Hajiaghayi

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Connectivity (05C40)

Abstract: The $k$-cut problem asks, given a connected graph $G$ and a positive integer $k$, to find a minimum-weight set of edges whose removal splits $G$ into $k$ connected components. We give the first polynomial-time algorithm with approximation factor $2-epsilon$ (with constant $epsilon>0$) for the $k$-cut problem in planar and minor-free graphs. Applying more complex techniques, we further improve our method and give a polynomial-time approximation scheme for the $k$-cut problem in both planar and minor-free graphs. Despite persistent effort, to the best of our knowledge, this is the first improvement for the $k$-cut problem over standard approximation factor of $2$ in any major class of graphs.

Recommendations

• scientific article; zbMATH DE number 2081002
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• A polynomial-time approximation scheme for planar multiway cut
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• On minimum 3-cuts and approximating k-cuts using cut trees

Cited in

(12)

• A polynomial-time bicriteria approximation scheme for planar bisection
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• scientific article; zbMATH DE number 6850341 (Why is no real title available?)
• scientific article; zbMATH DE number 6469225 (Why is no real title available?)
• scientific article; zbMATH DE number 2119718 (Why is no real title available?)
• Complexity and approximability of the \(k\)-way vertex cut
• Breaking the n ^k barrier for minimum k -cut on simple graphs
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
• An FPT algorithm beating 2-approximation for \(k\)-cut
• Fast and deterministic approximations for \(k\)-cut

This page was built for publication: Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs

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