2026-08-07T20:34:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12620 2024-03-06T10:51:16Z ddc:004 open_access

Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs Beideman, Calvin Chandrasekaran, Karthekeyan Xu, Chao Multiobjective Optimization Hypergraph min-cut Hypergraph-k-cut 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^{tr}n^{3t-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, Mahjoub, McCormick, and Queyranne [Aissi et al., 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^{r}n^{t+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 ∈ ℝ^t_+ is O(n²). 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 Queyranne [Guinez and Queyranne, 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 [Karger, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Calvin Beideman and Karthekeyan Chandrasekaran and Chao Xu 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.17 urn:nbn:de:0030-drops-126203 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.17 eng https://creativecommons.org/licenses/by/3.0/legalcode