Hypergraph k -Cut for Fixed k in Deterministic Polynomial Time

Karthekeyan Chandrasekaran () and Chandra Chekuri ()
Additional contact information
Karthekeyan Chandrasekaran: University of Illinois Urbana-Champaign, Champaign, Illinois 61820
Chandra Chekuri: University of Illinois Urbana-Champaign, Champaign, Illinois 61820

Mathematics of Operations Research, 2022, vol. 47, issue 4, 3380-3399

Abstract: We consider the H ypergraph - k -C ut 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 V 1 , V 2 , … , V k so as to minimize the cost of the hyperedges that cross the partition. G raph- k - C ut , the special case of H ypergraph - k -C ut obtained by restricting to graph inputs, has received considerable attention. Several different approaches lead to a polynomial-time algorithm for G raph- k - C ut 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 H ypergraph - k -C ut 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 H ypergraph - k -C ut 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 n O ( k 2 ) m time while the second one runs in n O ( 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 G raph- k - C ut .

Keywords: 68R10; hypergraphs; k -cut; algorithms (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1250 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:4:p:3380-3399

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().