TY - GEN
T1 - Multicriteria cuts and size-constrained k-cuts in hypergraphs
AU - Beideman, Calvin
AU - Chandrasekaran, Karthekeyan
AU - Xu, Chao
N1 - Funding Information:
Karthekeyan Chandrasekaran: Supported in part by NSF CCF-1907937 and CCF-1814613.
Publisher Copyright:
© 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2020/8/1
Y1 - 2020/8/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(r2trn3t−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 [1]. 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(r2rnt+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 ∈ Rt+ 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 Queyranne [11]. Our technique also shows that the number of optimal solutions is polynomial. All of our results build on the random contraction approach of Karger [12]. 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(r2trn3t−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 [1]. 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(r2rnt+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 ∈ Rt+ 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 Queyranne [11]. Our technique also shows that the number of optimal solutions is polynomial. All of our results build on the random contraction approach of Karger [12]. 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 min-cut
KW - Hypergraph-k-cut
KW - Multiobjective Optimization
UR - http://www.scopus.com/inward/record.url?scp=85091281474&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85091281474&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX/RANDOM.2020.17
DO - 10.4230/LIPIcs.APPROX/RANDOM.2020.17
M3 - Conference contribution
AN - SCOPUS:85091281474
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020
A2 - Byrka, Jaroslaw
A2 - Meka, Raghu
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020
Y2 - 17 August 2020 through 19 August 2020
ER -