TY - JOUR

T1 - Multicriteria cuts and size-constrained k-cuts in hypergraphs

AU - Beideman, Calvin

AU - Chandrasekaran, Karthekeyan

AU - Xu, Chao

N1 - Funding Information:
A preliminary version of this work appeared in the 24th International Conference on Randomization and Computation (RANDOM, 2020). This version contains complete proofs. Karthekeyan and Calvin were supported in part by NSF CCF-1907937 and CCF-1814613.
Funding Information:
We thank Maurice Queyranne and R. Ravi for encouraging us to study multicriteria min-cuts. We thank Rico Zenklusen for kindly agreeing to let us include his alternate proof of strongly polynomial bound on the number of multiobjective min-cuts in constant rank hypergraphs. We also thank the reviewers for their detailed review which helped improve the presentation of this work.
Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2023/1

Y1 - 2023/1

N2 - We address counting and optimization variants of multicriteria global min-cut and size-constrained min-k-cut in hypergraphs. 1.For an r-rank n-vertex hypergraph endowed with t hyperedge-cost functions, we show that the number of multiobjective min-cuts is O(r2 trn3t-1). In particular, this shows that the number of parametric min-cuts in constant rank hypergraphs for a constant number of criteria is strongly polynomial, thus resolving an open question by Aissi et al. (Math Program 154(1–2):3–28, 2015). In addition, we give randomized algorithms to enumerate all multiobjective min-cuts and all pareto-optimal cuts in strongly polynomial-time.2.We also address node-budgeted multiobjective min-cuts: For an n-vertex hypergraph endowed with t vertex-weight functions, we show that the number of node-budgeted multiobjective min-cuts is O(r2 rnt+2) , where r is the rank of the hypergraph, and the number of node-budgeted b-multiobjective min-cuts for a fixed budget-vector b∈R≥0t is O(n2).3.We show that min-k-cut in hypergraphs subject to constant lower bounds on part sizes is solvable in polynomial-time for constant k, thus resolving an open problem posed by Guinez and Queyranne (Unpublished manuscript. See also , 2012). Our technique also shows that the number of optimal solutions is polynomial. All of our results build on the random contraction approach of Karger (Proceedings of the 4th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 21–30, 1993). Our techniques illustrate the versatility of the random contraction approach to address counting and algorithmic problems concerning multiobjective min-cuts and size-constrained k-cuts in hypergraphs.

AB - We address counting and optimization variants of multicriteria global min-cut and size-constrained min-k-cut in hypergraphs. 1.For an r-rank n-vertex hypergraph endowed with t hyperedge-cost functions, we show that the number of multiobjective min-cuts is O(r2 trn3t-1). In particular, this shows that the number of parametric min-cuts in constant rank hypergraphs for a constant number of criteria is strongly polynomial, thus resolving an open question by Aissi et al. (Math Program 154(1–2):3–28, 2015). In addition, we give randomized algorithms to enumerate all multiobjective min-cuts and all pareto-optimal cuts in strongly polynomial-time.2.We also address node-budgeted multiobjective min-cuts: For an n-vertex hypergraph endowed with t vertex-weight functions, we show that the number of node-budgeted multiobjective min-cuts is O(r2 rnt+2) , where r is the rank of the hypergraph, and the number of node-budgeted b-multiobjective min-cuts for a fixed budget-vector b∈R≥0t is O(n2).3.We show that min-k-cut in hypergraphs subject to constant lower bounds on part sizes is solvable in polynomial-time for constant k, thus resolving an open problem posed by Guinez and Queyranne (Unpublished manuscript. See also , 2012). Our technique also shows that the number of optimal solutions is polynomial. All of our results build on the random contraction approach of Karger (Proceedings of the 4th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 21–30, 1993). Our techniques illustrate the versatility of the random contraction approach to address counting and algorithmic problems concerning multiobjective min-cuts and size-constrained k-cuts in hypergraphs.

KW - Hypergraph k-cuts

KW - Min cuts

KW - Multiobjective optimization

UR - http://www.scopus.com/inward/record.url?scp=85120182279&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85120182279&partnerID=8YFLogxK

U2 - 10.1007/s10107-021-01732-0

DO - 10.1007/s10107-021-01732-0

M3 - Article

AN - SCOPUS:85120182279

SN - 0025-5610

VL - 197

SP - 27

EP - 69

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -