On hypergraphs with
We give an algorithm that runs in
We give an algorithm that runs in
This content will become publicly available on December 13, 2024
We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems, namely, Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. The input in hypergraph k-partitioning problems is a hypergraph [Formula: see text] with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k nonempty parts [Formula: see text]—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 Minmax-Hypergraph-k-Partition. A subset of hyperedges is a minmax-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Minmax-Hypergraph-k-Partition. (2) If the objective of interest is the total cost of hyperedges crossing the k-partition, then the problem is known as Hypergraph-k-Cut. A subset of hyperedges is a min-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Hypergraph-k-Cut. We give the first polynomial bound on the number of minmax-k-cut-sets 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 [Formula: see text]-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known [Formula: see text]-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 Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).
Funding: All authors were supported by NSF AF 1814613 and 1907937.
more » « lessOn hypergraphs with
We give an algorithm that runs in
We give an algorithm that runs in
Assume [Formula: see text]. If [Formula: see text] is an ordinal and X is a set of ordinals, then [Formula: see text] is the collection of order-preserving functions [Formula: see text] which have uniform cofinality [Formula: see text] and discontinuous everywhere. The weak partition properties on [Formula: see text] and [Formula: see text] yield partition measures on [Formula: see text] when [Formula: see text] and [Formula: see text] when [Formula: see text]. The following almost everywhere continuity properties for functions on partition spaces with respect to these partition measures will be shown. For every [Formula: see text] and function [Formula: see text], there is a club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. For every [Formula: see text] and function [Formula: see text], there is an [Formula: see text]-club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. The previous two continuity results will be used to distinguish the cardinalities of some important subsets of [Formula: see text]. [Formula: see text]. [Formula: see text]. [Formula: see text]. It will also be shown that [Formula: see text] has the Jónsson property: For every [Formula: see text], there is an [Formula: see text] with [Formula: see text] so that [Formula: see text].