Counting and Enumerating Optimum Cut Sets for Hypergraph k -Partitioning Problems for Fixed k

Calvin Beideman (), Karthekeyan Chandrasekaran () and Weihang Wang ()
Additional contact information
Calvin Beideman: University of Illinois Urbana-Champaign, Urbana, Illinois 61801
Karthekeyan Chandrasekaran: University of Illinois Urbana-Champaign, Urbana, Illinois 61801
Weihang Wang: University of Illinois Urbana-Champaign, Urbana, Illinois 61801

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2579-2601

Abstract: We consider the problem of enumerating optimal solutions for two hypergraph k -partitioning problems, namely, H ypergraph - k -C ut and M inmax -H ypergraph - k -P artition . The input in hypergraph k -partitioning problems is a hypergraph G = ( V , E ) with positive hyperedge costs along with a fixed positive integer k . The goal is to find a partition of V into k nonempty parts ( V 1 , V 2 , … , V k ) —known as a k -partition—so as to minimize an objective of interest. (1) If the objective of interest is the maximum cut value of the parts, then the problem is known as M inmax -H ypergraph - k -P artition . A subset of hyperedges is a minmax - k - cut - set if it is the subset of hyperedges crossing an optimum k -partition for M inmax -H ypergraph - k -P artition . (2) If the objective of interest is the total cost of hyperedges crossing the k -partition, then the problem is known as H ypergraph - k -C ut . A subset of hyperedges is a min - k - cut - set if it is the subset of hyperedges crossing an optimum k -partition for H ypergraph - k -C ut . We give the first polynomial bound on the number of minmax - k - cut - set s and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed k . Our technique is strong enough to also enable an n O ( k ) p -time deterministic algorithm to enumerate all min - k - cut - set s in hypergraphs, thus improving on the previously known n O ( k 2 ) p -time deterministic algorithm, in which n is the number of vertices and p is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for H ypergraph - k -C ut and M inmax -H ypergraph - k -P artition . We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).

Keywords: Primary: 68R10; 05C65; hypergraphs; k -partition problems; algorithms; enumeration (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0259 (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:49:y:2024:i:4:p:2579-2601

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 ().