2020/09/25 by Karthekeyan Chandrasekaran, Chandra Chekuri, Chandrasekaran, Karthekeyan +1
Computer Science · #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2009.12442
openalex publication_date 2020/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the Hypergraph-k-cut problem. The input consists of a hypergraph G=(V,E) with non-negative hyperedge-costs c: E→ R+ and a positive integer k. The objective is to find a least-cost subset F⊆ E such that the number of connected components in G-F is at least k. An alternative formulation of the objective is to find a partition of V into k non-empty sets V1,V2,…,Vk so as to minimize the cost of the hyperedges that cross the partition. Graph-k-cut, the special case of Hypergraph-k-cut obtained by restricting to graph inputs, has received considerable attention. Several different approaches lead to a polynomial-time algorithm for Graph-k-cut when k is fixed, starting with the work of Goldschmidt and Hochbaum (1988). In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph-k-cut was developed (Chandrasekaran, Xu, Yu, 2018) via a subtle generalization of Karger's random contraction approach for graphs. In this work, we develop the first deterministic polynomial time algorithm for Hypergraph-k-cut for all fixed k. We describe two algorithms both of which are based on a divide and conquer approach. The first algorithm is simpler and runs in nO(k2) time while the second one runs in nO(k) time. Our proof relies on new structural results that allow for efficient recovery of the parts of an optimum k-partition by solving minimum (S,T)-terminal cuts. Our techniques give new insights even for Graph-k-cut.