TY - JOUR
T1 - Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
AU - Chandrasekaran, Karthekeyan
AU - Chekuri, Chandra
N1 - Funding Information:
Funding: This work was supported in part by the National Science Foundation [Grant CCF-1907937].
Publisher Copyright:
Copyright: © 2022 INFORMS.
PY - 2022/11
Y1 - 2022/11
N2 - We consider the HYPERGRAPH-k-CUT problem. The input consists of a hypergraph G = (V,E) with nonnegative hyperedge-costs c: E → R+ and a positive integer k. The objective is to find a minimum 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 nonempty 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 (Math of OR, 1994). In contrast, it is only recently that a randomized polynomial time algorithm for HYPERGRAPH-k-CUT was developed (Chandrasekaran, Xu, Yu, Math Programming, 2019) via a subtle generalization of Karger’s random contraction approach for graphs. In this work, we develop the first deterministic algorithm for HYPER-GRAPH-k-CUT that runs in polynomial time for any 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)m time while the second one runs in nO(k)m time, where n is the number of vertices and m is the number of hyperedges in the input hypergraph. 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.
AB - We consider the HYPERGRAPH-k-CUT problem. The input consists of a hypergraph G = (V,E) with nonnegative hyperedge-costs c: E → R+ and a positive integer k. The objective is to find a minimum 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 nonempty 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 (Math of OR, 1994). In contrast, it is only recently that a randomized polynomial time algorithm for HYPERGRAPH-k-CUT was developed (Chandrasekaran, Xu, Yu, Math Programming, 2019) via a subtle generalization of Karger’s random contraction approach for graphs. In this work, we develop the first deterministic algorithm for HYPER-GRAPH-k-CUT that runs in polynomial time for any 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)m time while the second one runs in nO(k)m time, where n is the number of vertices and m is the number of hyperedges in the input hypergraph. 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.
KW - algorithms
KW - hypergraphs
KW - k-cut
UR - http://www.scopus.com/inward/record.url?scp=85136088782&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85136088782&partnerID=8YFLogxK
U2 - 10.1287/moor.2021.1250
DO - 10.1287/moor.2021.1250
M3 - Article
AN - SCOPUS:85136088782
SN - 0364-765X
VL - 47
SP - 3380
EP - 3399
JO - Mathematics of Operations Research
JF - Mathematics of Operations Research
IS - 4
ER -