  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 (Math Programming, 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$ is $O(n^2)$.
  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. Our technique also shows that the number of
optimal solutions is polynomial.
  All of our results build on the random contraction approach of Karger (SODA,
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.
