Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time

We consider the Hypergraph- k-Cut problem. The input consists of a hypergraph G = (V, E) with nonnegative hyperedge-costs c: E→ \mathbbR+ 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) [1], [2]. In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph- k-Cut was developed [3] 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 n O(k2 ) time while the second one runs in n O(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.

Authors

• Karthekeyan Chandrasekaran
• Chandra Chekuri

Keywords

• Partitioning algorithms
• Complexity theory
• Approximation algorithms
• Monte Carlo methods
• Minimization
• Tools
• Standards
• Deterministic Time
• Deterministic Polynomial Time
• Positive Integer
• Random Approach
• Nonempty Set
• Graphical Approach
• Divide-and-conquer Approach
• Running Time
• Proof Of Theorem
• Cut Value
• Recursive Algorithm
• Proof Of The Lemma
• Part Of The Input
• Overview Of Techniques
• Lemma States
• Subset Of Vertices
• Partitioning Problem
• Related Work Section
• Key Lemma
• hypergraphs
• partition
• algorithms