TY - GEN

T1 - An FPT algorithm beating 2-approximation for k-cut

AU - Gupta, Anupam

AU - Lee, Euiwoong

AU - Li, Jason

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - In the k-Cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. Prior work on this problem gives, for all h 2 [2; k], a (2-ϵ/k)-approximation algorithm for k-cut that runs in time nO(h). Hence to get a (2-ϵ)-approximation algorithm for some absolute constant ", the best runtime using prior techniques is nO(k"). Moreover, it was recently shown that getting a (2-ϵ)-approximation for general k is NP-hard, assuming the Small Set Expansion Hypothesis. If we use the size of the cut as the parameter, an FPT algorithm to find the exact k-Cut is known, but solving the k-Cut problem exactly is W[1]-hard if we parameterize only by the natural parameter of k. An immediate question is: can we approximate k-Cut better in FPT-time, using k as the parameter? We answer this question positively. We show that for some absolute constant " > 0, there exists a (2-ϵ)-approximation algorithm that runs in time 2O(k6) O (n4). This is the first FPT algorithm that is parameterized only by k and strictly improves the 2-approximation.

AB - In the k-Cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. Prior work on this problem gives, for all h 2 [2; k], a (2-ϵ/k)-approximation algorithm for k-cut that runs in time nO(h). Hence to get a (2-ϵ)-approximation algorithm for some absolute constant ", the best runtime using prior techniques is nO(k"). Moreover, it was recently shown that getting a (2-ϵ)-approximation for general k is NP-hard, assuming the Small Set Expansion Hypothesis. If we use the size of the cut as the parameter, an FPT algorithm to find the exact k-Cut is known, but solving the k-Cut problem exactly is W[1]-hard if we parameterize only by the natural parameter of k. An immediate question is: can we approximate k-Cut better in FPT-time, using k as the parameter? We answer this question positively. We show that for some absolute constant " > 0, there exists a (2-ϵ)-approximation algorithm that runs in time 2O(k6) O (n4). This is the first FPT algorithm that is parameterized only by k and strictly improves the 2-approximation.

UR - http://www.scopus.com/inward/record.url?scp=85045571024&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045571024&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.179

DO - 10.1137/1.9781611975031.179

M3 - Conference contribution

AN - SCOPUS:85045571024

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2821

EP - 2837

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -