Breaking the n^k Barrier for Minimum k-cut on Simple Graphs

2021/11/05 by Zhiyang He, Jason Li, He, Zhiyang +1 · 1 citation
Computer Science · Mathematics · #05C85 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #math.CO #msc:05C85

paper · pdf · doi:10.48550/arxiv.2111.03221

arxiv created 2021/12/01 · arxiv updated 2021/12/02

Abstract

In the minimum k-cut problem, we want to find the minimum number of edges whose deletion breaks the input graph into at least k connected components. The classic algorithm of Karger and Stein runs in O(n^2k-2) time, and recent, exciting developments have improved the running time to O(n^k). For general, weighted graphs, this is tight assuming popular hardness conjectures. In this work, we show that perhaps surprisingly, O(n^k) is not the right answer for simple, unweighted graphs. We design an algorithm that runs in time O(n^(1-ε)k) where ε>0 is an absolute constant, breaking the natural n^k barrier. This establishes a separation of the two problems in the unweighted and weighted cases.

Cited by

• Sub-n^k Deterministic algorithm for minimum k-way cut in simple graphs

Related

• Faster Minimum k-cut of a Simple Graph
• The Karger-Stein Algorithm is Optimal for k-cut
• Faster Exact and Approximate Algorithms for k-Cut
• The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
• Fast and Deterministic Approximations for k-Cut