PaperlayerView exact revision on arXiv

Source-linked AI summary

A Polymatroidal Perspective on Random Contraction

Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu

arXiv:2609.04521v1cs.DS

TL;DR

Existing random-contraction algorithms for graph, hypergraph, and hedgegraph mincuts motivate a common framework for finding minimum polymatroid quotients. The paper introduces quotient-bounded families and shows that random-contraction variants recover several existing algorithmic results.

  • Problem

    The paper asks whether random-contraction results for graph, hypergraph, and hedgegraph mincuts can be understood in a common framework, despite minimum-quotient hardness for general matroids.

    Source: §1 · p. 2

  • Method

    The paper defines quotient-bounded polymatroid families and analyzes random-contraction variants that distinguish elements by their polymatroid values.

    Source: §1 · pp. 4–5

  • Results

    The framework recovers polynomial-time minimum-quotient algorithms for strongly quotient-bounded families, PTAS and quasi-polynomial algorithms for quotient-bounded families, and an FPT algorithm parameterized by solution size.

    Source: §1.1 · p. 6

  • Takeaways & Limitations

    The results place several existing graph, hypergraph, and hedgegraph mincut algorithms within a shared polymatroidal framework.

    Source: §8 · p. 30

    The work focuses on defining quotient-bounded classes and unifying known mincut results, leaving formal verification for some tractable matroid families to future work.

    Source: §1.1 · p. 7

Abstract

from arXiv · show

Karger's elegant random contraction algorithm for finding a global mincut in a graph has been highly influential. More recent work has obtained several different (nonuniform) random contraction algorithms for mincut in hypergraphs and hedgegraphs. Motivated by the conceptual goal of understanding these algorithms in a unified fashion, we study random contraction algorithms for finding a minimum quotient of a polymatroid. We introduce the notion of quotient-bounded polymatroids and show that several existing results can be derived and understood under a common algorithmic framework for quotient-bounded polymatroids.

1 Introduction

The introduction frames random contraction as a shared approach to minimum cuts in graphs, hypergraphs, and hedgegraphs, then develops a polymatroidal framework for understanding when these methods find minimum quotients. It states algorithmic and counting results for quotient-bounded families and situates them among related work.

1 Introduction

  • Random contraction results for graphs, hypergraphs, and hedgegraphs motivate a unified polymatroidal framework, although finding a minimum quotient is NP-hard even for restricted matroid classes.The framework aims to explain existing algorithms and support new results; the paper leaves verification of some matroid families for future work.Source: §1 · pp. 2–3, §1.1 · p. 7
  • The paper defines quotient-bounded polymatroid families and distinguishes strong from ordinary quotient-boundedness, with the strong condition especially relevant to random contraction.For k-polymatroids, the two notions are equivalent up to a factor of 2k.Source: §1 · pp. 4–5
  • Graphs, hypergraphs, and hedgegraphs are 2-quotient-bounded; hypergraphs are 1-strongly-quotient-bounded, while hedgegraphs of span at most s are s-strongly-quotient-bounded.The paper states these structural properties are proved in Section 7.Source: §1 · p. 5

1.1 Our Results

  • For c-strongly-quotient-bounded families, the paper gives a polynomial-time minimum-quotient algorithm, recovering algorithms for bounded-span hedgegraphs, hypergraphs, and graphs [11].Its stated running time is (r · n)^O(c).Source: §1.1 · pp. 5–6
  • For c-quotient-bounded families, the paper gives a PTAS and quasi-polynomial exact algorithm, recovering hedgegraph results [19], plus an FPT algorithm parameterized by quotient size q, recovering [14].The stated running times are r^O(c log(1/ε))n^O(c), r^O(c log q)n^O(c), and 2^q · r^O(c log c) · n^O(c), respectively.Source: §1.1 · p. 6
  • For c-strongly-quotient-bounded k-polymatroids, the algorithm captures every fixed α-approximate minimum quotient with probability Ω(k^-1r^-(c+1)α) and leaves rank at most α(c + k).The paper uses this result to derive a bound on approximate minimum cuts in k-hypergraphs, improving on an intermediate bound that it describes as weaker than Kogan–Krauthgamer’s.Source: §1.1 · pp. 6–7

1.2 Related Work

  • Related work includes random-contraction algorithms for min k-cut in graphs, hypergraphs, and constant-span hedgegraphs, while extending these approaches to polymatroids remains future work.The introduction also points to work on faster contraction algorithms, network unreliability, sparsification, and matroid cogirth.Source: §1.2 · p. 7

2 Preliminaries

The preliminaries define polymatroid rank, deletion, contraction, and quotients, then give basic facts about how quotients behave under these operations.

2 Preliminaries

  • A polymatroid has rank r = f(N); deleting A restricts f to subsets outside A, while contracting A gives f(S ∪ A) − f(A).Both operations yield polymatroids.Source: §2 · pp. 7–8
  • A quotient Q is a subset whose complement is closed, where closedness means adding any outside element increases the set's function value.The empty set is always a quotient.Source: §2 · p. 7
  • Deleting elements preserves quotients: Q \ T is a quotient after deleting T, and deleting an element of a minimum quotient preserves minimality after removing that element from Q.Contracting an element outside a minimum quotient preserves that quotient as minimum.Source: §2 · p. 8
  • A polymatroid of rank r on n elements has at most nr non-empty quotients.The text defers proofs of the preliminary lemmas to Appendix A.Source: §2 · p. 8

3 Min-Quotient in c-strongly-quotient-bounded polymatroids

For strongly quotient-bounded polymatroid families, the section analyzes a nonuniform random-contraction algorithm that returns a collection containing any fixed minimum quotient with inverse-polynomial probability. Repetition yields a polynomial-time algorithm for finding a minimum quotient.

3 Min-Quotient in c-strongly-quotient-bounded polymatroids

  • For c-strongly-quotient-bounded families, a random-contraction algorithm finds a minimum quotient in time (r · n)^O(c) with high probability.A single run returns n^O(c) quotients and contains any fixed minimum quotient with probability at least 1/r^O(c).Source: §3 · p. 8

3.1 Non-uniform Random Contraction Algorithm

  • When an element has f(e) ≥ r − c, the algorithm branches by deleting it and enumerating quotients after contracting it; otherwise it samples an element with probability proportional to r − f(e) − c and contracts it.It removes zero-value elements first and recurses toward a small-rank brute-force case.Source: §3.1 · p. 9
  • For any polymatroid, Algorithm 1 returns n^(c+1) quotients in n^O(c) time.The section bounds output size by induction and runtime by a recurrence over decreasing ground-set size.Source: §3.1 · pp. 9–10

3.2 Success Probability Analysis

  • For each fixed minimum quotient, the algorithm's output collection contains it with probability at least 1/r^O(c).The proof applies strong quotient-boundedness in only one inequality of the success-probability analysis.Source: §3.2 · pp. 10–11

4 Min-Quotient in c-quotient-bounded polymatroids

For c-quotient-bounded polymorphisms, the section develops a randomized contraction algorithm for approximate minimum quotients and derives guarantees for approximation and exact search.

4 Min-Quotient in c-quotient-bounded polymatroids

  • A quotient of size at most (1 + ε)·q is returned with probability at least 1/r^O(c·log(1/ε)); repetition yields a high-probability approximation in time r^O(c log(1/ε))n^O(c).Here r is the rank and q is the minimum non-empty quotient size.Source: §4 · pp. 11–12
  • With high probability, an exact minimum quotient can be found in time r^O(c log q)n^O(c), where q is its minimum size.The section also bounds the number of minimum non-empty quotients by r^O(c log q)n^O(c).Source: §4 · p. 12

4.1 Randomized Algorithm

  • Algorithm 2 returns n^4c quotients in n^O(c) time, using heavy/moderate-element branching and random contraction when no heavy element exists.For a heavy/moderate set L, it either deletes L and cleans up the resulting quotients or contracts a uniformly random element of L; with no heavy element, it contracts a uniformly random element.Source: §4.1 · p. 13

4.2 Success Probability Analysis

  • A single execution performs at most 4c·log r branching steps, and the returned collection contains a (1 + ε)-approximate minimum quotient with probability at least 1/r^O(c log(1/ε)).The probability guarantee is established for every c-quotient-bounded family and input polymatroid.Source: §4.2 · pp. 14–15

5 FPT of Min-Quotient in c-quotient-bounded polymatroids

For c-quotient-bounded polymorphisms, the section gives a randomized fixed-parameter algorithm for exact minimum quotients. Its collection contains each fixed optimum with a stated probability, yielding an exact algorithm parameterized by quotient size.

5 FPT of Min-Quotient in c-quotient-bounded polymatroids

  • Theorem 3 returns n^O(c) quotients in polynomial time, and the collection contains each fixed minimum quotient with probability at least 1/(2^q·r^O(c log c)).Here q is the minimum quotient size and r is the rank.Source: §5 · p. 18
  • For fixed c, the algorithm finds a minimum quotient with high probability in time 2^q·r^O(c log c)·n^O(c).When q is unknown, it tries successive size guesses and stops at the first guess for which it returns a quotient of at most that size.Source: §5 · p. 18
  • The number of minimum non-empty quotients is at most 2^q·r^O(c log c)·n^O(c).Here r, n, and q denote rank, ground-set size, and minimum quotient size, respectively.Source: §5 · p. 18

5.1 Randomized Algorithm

  • Algorithm 3 returns n^2c quotients in n^O(c) time, using heavy-element branching and independent 1/q sampling of elements when all are light.For a heavy element it branches between deleting it and contracting it; the light-element branch contracts the sampled set.Source: §5.1 · p. 19

5.2 Success Probability Analysis

  • For every fixed minimum non-empty quotient Q of size q, Algorithm 3’s returned collection contains Q with probability at least an unspecified lower bound.When r + q ≤ 4c, Algorithm 3 uses brute-force search and contains Q in its returned collection with probability 1.Source: §5.2 · p. 23

6 Min-Quotient in c-strongly-quotient-bounded k-polymatroids

This section gives a uniform random-contraction algorithm for c-strongly-quotient-bounded k-polymatroid families. It bounds the rank left after contraction and guarantees that each α-approximate minimum quotient survives with stated probability.

Theorem 4

  • The algorithm returns a subset whose complement contraction has rank at most α(c + k), while retaining every α-approximate minimum quotient with probability Ω(k^-1 r^(-(c+1)α)).The guarantee applies to c-strongly-quotient-bounded k-polymatroid families.Source: §6 · p. 25

Uniform random contraction

  • It repeatedly contracts a uniformly sampled positive-value element, stopping when the polymatroid rank is at most α(c + k).At the stopping threshold, the algorithm returns the whole ground set.Source: §6 · pp. 25–26

Survival analysis

  • The contraction step preserves a fixed α-approximate minimum quotient whenever the sampled element is outside it, allowing the analysis to recurse on the contracted polymatroid.The minimum quotient size does not decrease under contraction, supporting the induction on rank.Source: §6 · p. 27

Scope

  • For c-quotient-bounded k-polymatroid families, the section reports similar results, with details deferred to Appendix C.Source: §6 · p. 28

7 Graphs, Hypergraphs, and Hedgegraphs

The section places graph, hypergraph, and hedgegraph cut problems in the quotient-bounded polymatroid framework. It establishes bounds for hedgegraphs by span and derives a count of approximate min-cuts in k-hypergraphs.

Hedgegraphs

  • Hedgegraph polymatroids of span at most s form a minor-closed, s-strongly-quotient-bounded family.Source: §7 · p. 28

Graphs and hypergraphs

  • Graphs and hypergraphs are hedgegraphs of span at most 1, so their polymatroid families are 1-strongly-quotient-bounded.Source: §7 · p. 29

Hedgegraphs

  • All hedgegraph polymatroids are minor-closed and 2-quotient-bounded; this implies that graph and hypergraph polymatroid families are 2-quotient-bounded.Source: §7 · p. 29

Hypergraphs

  • For connected k-hypergraphs, the number of α-approximate min-cuts is O(2^(αk) · k · n^(2α)).Source: §7 · p. 30

8 Conclusion

The conclusion presents quotient-bounded polymatroids as a setting where random contraction can solve min-quotient, despite hardness for arbitrary matroids. It leaves deterministic algorithms and additional suitable polymatroid families as open directions.

Contributions

  • The paper introduces quotient-bounded polymatroids as a subfamily for which random contraction gives efficient min-quotient algorithms, while min-quotient is NP-hard in arbitrary matroids.Source: §8 · p. 30

Open directions

  • The authors ask whether the randomized polynomial-time algorithm for c-strongly-quotient-bounded families can be made deterministic, and whether other such families exist.They note that a deterministic algorithm would yield deterministic min-cut algorithms for constant-span hedgegraphs.Source: §8 · p. 30

A Missing Proofs from Section 2

The appendix records how quotients behave under deletion and contraction, then bounds the number of non-empty quotients using rank and ground-set size.

Lemma 1

  • Deleting elements preserves quotients after removing the deleted elements; deleting one element of a minimum quotient preserves minimality when that quotient has size greater than one.Source: A Missing Proofs from Section 2 · p. 34
  • Contracting an element outside a minimum quotient preserves that quotient's minimality, and contraction cannot decrease the minimum non-empty quotient size.Source: A Missing Proofs from Section 2 · p. 34

Lemma 2

B Proof of Corollary 5

The proof bounds the chance that Search returns a fixed minimum non-empty quotient, using induction on rank and branching steps. Its case analysis preserves the quotient through contractions or deletions.

B Proof of Corollary 5

  • At least 1/r^O(c log q) is the probability that Algorithm 2 returns any fixed minimum non-empty quotient of a rank-r polymatroid in a c-quotient-bounded family.Here q is the quotient’s size.Source: B Proof of Corollary 5 · p. 35
  • The induction is on r + ℓ, with a brute-force base case when r + ℓ ≤ 4c; zero-valued elements are excluded from Q by definition and removed in Step 2.The analysis assumes ℓ ≤ 4c · log r.Source: B Proof of Corollary 5 · p. 36
  • When a contracted element lies outside Q, Q remains minimum in the contracted polymatroid, so the recursive call can preserve it.The contraction reduces rank; the proof uses this recurrence in its light/moderate-element case.Source: B Proof of Corollary 5 · p. 36
  • When L is nonempty and L \ Q is empty, the algorithm either returns Q = L or recurses after deleting L, preserving Q \ L.The recursive call includes Q \ L with probability at least P(r, ℓ−1).Source: B Proof of Corollary 5 · p. 37
  • When L \ Q is nonempty, contracting a uniformly sampled element of L preserves Q whenever the sampled element lies outside Q.The probability of that event is |L \ Q|/|L|.Source: B Proof of Corollary 5 · p. 37

C Min-Quotient in c-quotient-bounded k-polymatroids

For c-quotient-bounded k-polymatroids, the paper gives a polynomial-time uniform random contraction algorithm that returns a subset containing each α-approximate minimum quotient with a stated probability, while bounding the rank after contraction.

C Min-Quotient in c-quotient-bounded k-polymatroids

  • The algorithm returns a subset containing each α-approximate minimum quotient with probability at least Ω(k^-1 r^-cα), while contracting the complement leaves rank at most cαk.These guarantees apply to c-quotient-bounded k-polymatroid families.Source: C Min-Quotient in c-quotient-bounded… · p. 38
  • Theorem 5 specifies a randomized algorithm with evaluation-oracle access that returns a subset of the ground set in polynomial time.Its two stated guarantees are the rank bound and probability of containing each target quotient.Source: C Min-Quotient in c-quotient-bounded… · p. 38
  • The algorithm uses uniform random contraction of positive-value elements until rank is at most cαk, when it returns the whole ground set.The described contraction recurses on the contracted polymatroid.Source: C Min-Quotient in c-quotient-bounded… · pp. 38–39
  • The proof tracks a fixed α-approximate minimum quotient through contractions, using that it remains approximate when the contracted element is outside it.The rank decreases by the contracted element’s value, and the induction supplies the recursive survival bound.Source: C Min-Quotient in c-quotient-bounded… · p. 40

D Proof of Lemmas 11 and 16

The appendix proves Lemmas 11 and 16 by analyzing feasible solutions to their linear programs. In both arguments, tightness constraints restrict the possible forms of an optimum.

D Proof of Lemmas 11 and 16

  • The appendix establishes lower bounds on the optimum values of LP-(10) and LP-(15), under their respective rank conditions.Lemma 11 assumes r > α(c + k); Lemma 16 assumes r > cαk.Source: D Proof of Lemmas 11 and 16 · pp. 41–42
  • For LP-(10), the last constraint must be tight at an optimum, leaving at most two non-tight constraints among the 2k bounds 0 ≤ yi ≤ xi.The proof then analyzes the possible cases for those constraints.Source: D Proof of Lemmas 11 and 16 · p. 42
  • For LP-(15), the same tightness argument limits an optimum to at most two non-tight constraints among the 2k bounds 0 ≤ yi ≤ xi.This reduces the proof to a case analysis of the possible constraint patterns.Source: D Proof of Lemmas 11 and 16 · p. 43
Loading 2609.04521v1…