PaperlayerView exact revision on arXiv

Source-linked AI summary

Multicritera Cuts and Size-Constrained $k$-cuts in Hypergraphs

Calvin Beideman, Karthekeyan Chandrasekaran, Chao Xu

arXiv:2006.11589v1cs.DScs.DM

TL;DR

The paper asks whether multicriteria min-cuts admit strongly polynomial counting bounds and whether size-constrained min-k-cut can be solved in polynomial time. It uses random-contraction analysis to bound cut counts and solve the constrained problem, obtaining polynomial bounds and algorithms.

  • Problem

    The paper asks whether multiobjective min-cuts can be counted in strongly polynomial numbers and whether lower-bounded size-constrained min-k-cut is polynomial-time solvable.

    Source: §1 · p. 2

  • Method

    Random contraction supports interleaving to count multiobjective cuts across budgets; for size constraints, non-uniform contractions and weight tracking handle arbitrary constant sizes.

    Source: §1.2 · pp. 6–7

  • Results

    O(n^{3t-1}) bounds all multiobjective min-cuts across budget vectors in constant-rank hypergraphs; randomized enumeration algorithms are given, and size-constrained min-k-cut is polynomial-time for constant k and sizes.

    Source: §1.1 · p. 4, §1.2 · p. 6

  • Takeaways & Limitations

    For constant-rank hypergraphs with a constant number of criteria, the Pareto-optimal-cut count is strongly polynomial, answering an open question.

    Source: §1.1 · p. 4

    The interleaving argument does not extend to arbitrary-rank hypergraphs; strong-polynomial bounds for their parametric min-cuts remain unknown.

    Source: §1.2 · pp. 6–7

Abstract

from arXiv · show

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.

1 Introduction

The paper studies multicriteria and size-constrained cut problems in hypergraphs, using random contraction to develop counting bounds and optimization algorithms for multiobjective and node-budgeted min-cuts and for size-constrained min-k-cut.

1.1 Our Contributions

  • O(r2^(rt)n^(3t−1)) bounds multiobjective min-cuts in rank-r hypergraphs, and the resulting O(n^(3t−1)) Pareto-optimal-cut bound resolves an open question for constant rank and criteria.The authors also give randomized polynomial-time algorithms to enumerate both sets of cuts.Source: §1.1 · p. 4
  • Ω(n^t) Pareto-optimal cuts are attained by a constructed graph with t edge-cost functions, and the same lower bound holds for fixed-budget b-multiobjective min-cuts.This improves the previously stated Ω(n^(t/2)) lower bound for Pareto-optimal cuts and multiobjective min-cuts.Source: §1.1 · p. 4
  • O(r2^r n^(t+2)) bounds node-budgeted multiobjective min-cuts in rank-r hypergraphs, while O(n^2) bounds node-budgeted b-multiobjective min-cuts for a fixed budget vector, even at arbitrary rank.The first result is strongly polynomial for constant rank and t; the fixed-budget result is strongly polynomial at arbitrary rank for any t.Source: §1.1 · p. 4
  • Polynomial time suffices for size-constrained min-k-cut in arbitrary-rank hypergraphs when k and all part-size lower bounds are fixed, and the number of optimal cuts over vertex-weight functions is polynomial.This resolves an open problem posed by Guinez and Queyranne.Source: §1.1 · pp. 4–5

1.2 Technical Overview

  • Uniform random contractions enable an interleaving argument: modified contractions find a fixed budgeted multiobjective min-cut with probability Ω(n^(−2t)), yielding O(n^(3t−1)) multiobjective min-cuts in constant-rank hypergraphs.For hypergraphs, an LP-based analysis extends the success-probability argument, and the interleaving argument proceeds similarly to the graph case.Source: §1.2 · p. 6
  • The interleaving argument does not extend to arbitrary-rank hypergraphs because known random-contraction algorithms use non-uniform contractions, preventing the criterion-wise permutations from being uniformly random.The authors also report large-rank instances on which the approaches of Aissi, Mahjoub, and Ravi [2] and their modified approach never succeed, even with non-uniform contractions.Source: §1.2 · p. 7
  • For node-budgeted cuts, contracting infeasible vertices together with random contractions finds a fixed budgeted cut with probability Ω(n^(−2)); an improved interleaving-like argument gives O(n^(t+2)) cuts in constant-rank hypergraphs.The method uses uniform contractions for constant-rank and non-uniform contractions for arbitrary-rank hypergraphs.Source: §1.2 · p. 7
  • For size-constrained min-k-cut, non-uniform contractions extend to arbitrary constant part sizes, while weight tracking lets the algorithm succeed for any vertex-weight function without taking it as input.For unit sizes and unit weights, its success probability is weaker by a factor of n than the algorithm of Chandrasekaran, Xu, and Yu.Source: §1.2 · p. 7
  • The constraint requires 0 ≤ y_j ≤ x_j for every j ∈ {2, ..., r}.Source: §1.2 · p. 8

2 Multiobjective Min-Cuts and Pareto-Optimal Cuts

This section studies randomized contraction methods for multiobjective and Pareto-optimal cuts, including algorithms for testing and enumerating such cuts in polynomial time. It also establishes bounds on the numbers of Pareto-optimal and budget-constrained multiobjective min-cuts.

2 Multiobjective Min-Cuts and Pareto-Optimal Cuts

  • The section establishes an Ω(n^t) lower bound on the numbers of Pareto-optimal cuts and b-multiobjective min-cuts.Source: §2 · p. 8

2.1 Finding b-Multiobjective Min-Cuts

  • Algorithm 1 uses randomized contraction to find a b-multiobjective min-cut and can be implemented in polynomial time.Theorem 2.1 gives a success-probability guarantee for any fixed b-multiobjective min-cut.Source: §2.1 · pp. 8–9

2.2 Finding Multiobjective Min-Cuts

  • Algorithm 2 returns at most n^(t−1) cuts and includes any fixed multiobjective min-cut with inverse-polynomial probability.It does not require a budget-vector as input; its randomness, apart from the base case, comes from selecting hyperedge permutations upfront.Source: §2.2 · pp. 12–13
  • O(r2^rt n^(3t−1)) bounds the number of multiobjective min-cuts in an r-rank, n-vertex hypergraph with t hyperedge-cost functions.The same upper bound applies to Pareto-optimal cuts because they are a subset of multiobjective min-cuts.Source: §2 · p. 8, §2.2 · p. 14

2.3 Enumerating Multiobjective Min-Cuts and Pareto-Optimal Cuts

  • Repeated calls to Algorithm 2 produce a superset of all multiobjective min-cuts with high probability, which can be pruned to identify them in polynomial time.The section also gives a polynomial-time procedure for checking Pareto optimality, using the b-multiobjective min-cut algorithm with different budget-vectors.Source: §2.3 · pp. 14–15
  • The polynomial-time test returns TRUE for Pareto-optimal cuts and returns FALSE for non-Pareto-optimal cuts with high probability.It tests whether a budget-constrained multiobjective min-cut can reveal a cut that dominates the input.Source: §2.3 · p. 15

2.4 Lower Bounds

  • For constant t, some n-vertex graphs have Ω(n^t) distinct Pareto-optimal cuts.The construction uses t paths between two vertices; cuts containing exactly one edge from each path are Pareto-optimal.Source: §2.4 · pp. 15–16
  • Some budget vector has Ω(n^t) b-multiobjective min-cuts, with each of its t−1 budget values equal to 2t/(t + 1).This bound is distinct from the Pareto-optimal-cut bound: neither bound implies the other.Source: §2.4 · p. 16

3 Node-Budgeted Multiobjective Min-Cuts

This section develops polynomial-time algorithms and counting bounds for node-budgeted multiobjective min-cuts in hypergraphs, using random contraction and a non-uniform extension for arbitrary-rank hypergraphs. It also analyzes the arbitrary-rank b-multiobjective contraction algorithm by induction, distinguishing cases according to whether the feasible-vertex set fits the budgets.

3.1 Constant-Rank Hypergraphs

  • A fixed node-budgeted b-multiobjective min-cut in a constant-rank hypergraph is returned with probability at least 1/(2^(r+1) C(n,2)) by a polynomial-time algorithm.The algorithm combines random hyperedge contraction with deterministic contraction of all infeasible vertices.Source: §3.1 · p. 17
  • The proof concludes that the number of node-budgeted multiobjective min-cuts is O(r2^r n^(t+2)), although Theorem 3.2 states O(r2^r n^(t+1)).Algorithm 6 constructs at most r·O(n^t) candidate cuts, with each fixed-budget cut included with probability Ω(2^-r n^-2).Source: §3.1 · pp. 20–21

3.2 Arbitrary-Rank Hypergraphs

  • For arbitrary-rank hypergraphs, the section extends non-uniform random contraction to node-budgeted cuts and gives a polynomial-time algorithm with a correctness-probability guarantee.The algorithm contracts infeasible vertices after each contraction and uses the ordinary non-uniform hypergraph min-cut algorithm as a subroutine.Source: §3.2 · pp. 21–22
  • Contracting multiple infeasible vertices together preserves the probability of returning F and reduces the instance to one with at most one infeasible vertex.The proof then applies its induction hypothesis to the reduced hypergraph.Source: §3.2 · p. 23
  • When U is feasible and at most one vertex is infeasible, every cut is feasible, so the problem reduces to an ordinary minimum cut.The proof applies the Hypergraph Min-Cut algorithm to F in this case.Source: §3.2 · pp. 23–24
  • If U is not feasible, the algorithm contracts a randomly chosen hyperedge with probability proportional to αe and uses induction on the contracted instance.The proof treats the case αe = 0 for every edge separately: if U is feasible, F = δ(U); otherwise F = E.Source: §3.2 · pp. 23–24
  • A uniformly random feasible vertex induces a cut whose expected value bounds the optimum and yields c(F) ≤ c(E \ F).The proof derives the bound by relating the expected cut value to the sum of αe over hyperedges.Source: §3.2 · p. 25

4 Size-Constrained Min-k-Cut in Arbitrary-Rank Hypergraphs

For fixed k and fixed part-size lower bounds, the paper gives a polynomial-time algorithm for size-constrained min-k-cut in hypergraphs. Its random-partition and random-contraction approach has an inverse-polynomial success bound and extends to multiple vertex-weight constraints.

4 Size-Constrained Min-k-Cut in Arbitrary-Rank Hypergraphs

  • For fixed k and fixed lower bounds s, a polynomial-time algorithm finds a minimum-cost size-constrained k-cut with probability at least Q_n.The theorem covers nonnegative hyperedge costs and fixed positive integer vertex weights.Source: §4 · pp. 25, 28
  • Algorithm 9 samples a k-partition and recursively contracts a random hyperedge; each recursive call reduces the vertex count, so there are at most n calls.The exposition focuses on the cardinality variant, while the algorithm also extends to nonnegative hyperedge costs.Source: §4 · pp. 25–26
  • Q_n = Ω(k^-σ_k−1−σ_k n^-2σ_k−1−1), giving an inverse-polynomial success bound when k and the size bounds are fixed.Here σ_k−1 is the sum of the first k−1 size bounds.Source: §4 · pp. 25–26
  • With t vertex-weight functions, the algorithm can satisfy each function’s part-size lower bounds by using the coordinatewise maximum lower bound for each part.The resulting cut is found with at least inverse-polynomial probability.Source: §4 · pp. 29–30

5 Conclusion and Open Problems

The conclusion presents random contraction as a versatile approach for multicriteria min-cut and size-constrained min-k-cut problems. It highlights remaining gaps in counting bounds and asks whether b-multiobjective min-cut is tractable in arbitrary-rank hypergraphs.

5 Conclusion and Open Problems

  • For pareto-optimal cuts and multiobjective min-cuts, the lower bound Ω(n^t) and upper bound O(n^(3t−1)) still leave a gap.The paper suggests improving the fixed-budget b-multiobjective min-cut bound as a possible first step.Source: §5 · p. 30
  • The paper uses random contraction to address multicriteria min-cut and size-constrained min-k-cut problems.The conclusion frames this as illustrating the technique’s versatility.Source: §5 · p. 30
  • Whether b-multiobjective min-cut is polynomial-time solvable or NP-hard in arbitrary-rank hypergraphs remains open, even for t = 2 criteria.The paper reports a polynomial-time algorithm for constant-rank hypergraphs.Source: §5 · p. 30

A.1 Comparison of Parametric, Pareto-Optimal, and Multiobjective Cuts

The cut classes form a containment chain: parametric min-cuts are pareto-optimal, which are in turn multiobjective min-cuts. Both containments can be strict.

A.1 Comparison of Parametric, Pareto-Optimal, and Multiobjective Cuts

  • The containment relationship may be strict.This proposition is supported by the two counterexamples to the reverse containments.Source: §A.1 · p. 31
  • Parametric min-cuts are pareto-optimal, but some pareto-optimal cuts are not parametric min-cuts.The passage gives Figure 10 as an example of the strict containment.Source: §A.1 · p. 31
  • Every pareto-optimal cut is a b-multiobjective min-cut for the budget vector b_i = c_i(F), for each i in [k − 1].Some multiobjective min-cuts are not pareto-optimal; Figure 11 gives an example for b = 2.Source: §A.1 · p. 31

A.2 Proof of Lemma 1.4

The appendix proves Lemma 1.4 by reducing the linear program to extreme-point cases and deriving its optimum as a minimum over indices from 2 to r.

A.2 Proof of Lemma 1.4

  • The optimum of LP1 is min over 2 ≤ j ≤ r of (1 − j/(γ − r + j)) f(n − j + 1).The lemma assumes positive integers n ≥ γ ≥ r + 1 > 2 and a positive-valued function f.Source: §A.2 · p. 31
  • LP1 is feasible and bounded, so it has an extreme-point optimum with at most two non-tight constraints.Feasibility follows by setting x_2 = 1 and the other variables to zero; boundedness follows from the objective being bounded above by a sum of f-values.Source: §A.2 · p. 32
  • Constraint (4) must be tight at every optimum, since otherwise increasing a slack y_j improves the objective while preserving feasibility.At least one y_j ≤ x_j constraint is slack, because making all y_j = x_j would violate constraint (4).Source: §A.2 · p. 32
  • The proof considers whether the two slack constraints share an index, then compares the resulting LP objective values to obtain the minimum.The cases are j_1 = j_2 and j_1 ≠ j_2; the proof simplifies each case before taking the smaller value.Source: §A.2 · pp. 32–33

A.3 Proof of Proposition 4.1

The section restates and proves Proposition 4.1 by splitting the proof into cases on e.

A.3 Proof of Proposition 4.1

  • Proposition 4.1 is stated for positive integers n, e, and σ with e ≥ 2 and n − e + 1 > 2σ.Source: §A.3 · p. 33
  • The proof treats e > σ as a separate case and lower-bounds expression (16).Source: §A.3 · p. 34
  • For e ≤ σ, expression (17) increases as e is incremented, so it is minimized at the smallest considered value, e = 2.The proof uses (n−e−σ)(n−e+1) and (n−2σ−e+1)(n−e) > 1.Source: §A.3 · p. 34
Loading 2006.11589v1…