License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.17
URN: urn:nbn:de:0030-drops-126203
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12620/
Go to the corresponding LIPIcs Volume Portal

Beideman, Calvin ; Chandrasekaran, Karthekeyan ; Xu, Chao

Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs

pdf-format:
LIPIcs-APPROX17.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{beideman_et_al:LIPIcs:2020:12620,
  author =	{Calvin Beideman and Karthekeyan Chandrasekaran and Chao Xu},
  title =	{{Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12620},
  URN =		{urn:nbn:de:0030-drops-126203},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.17},
  annote =	{Keywords: Multiobjective Optimization, Hypergraph min-cut, Hypergraph-k-cut}
}

Keywords: Multiobjective Optimization, Hypergraph min-cut, Hypergraph-k-cut
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI