Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
Lists
Only you see this
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 – ∊ (with constant ∊ > 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.
BibTeX
@inproceedings{bateni2019polynomial,
author = {MohammadHossein Bateni and Alireza Farhadi and MohammadTaghi Hajiaghayi},
title = {{Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs}},
booktitle = {SODA},
year = {2019},
url = {https://openreview.net/forum?id=kUqTMexnrn},
}