Source-linked AI summary
Sharp Bounds on the Number of Small Cuts
Chao Xu, Mingdong Yang
TL;DR
The paper addresses the strict cut-count bound for cuts below a multiple of the minimum cut. It proves the strict version using recurrence, vertex sampling, and splitting off; the exponent is sharp and improves by one when 2α is an integer.
Problem
The paper addresses the strict version of the cut-count bound, resolving an open problem posed by Henzinger and Williamson and Karger.
Source: §1 · p. 1Method
The proof extends a recurrence to fixed numbers of terminals, samples vertices to distinguish incomparable sets, splits off other vertices, and applies Theorem 1 to the smaller graph.
Source: §1 · p. 2Results
The exponent is sharp for every fixed α > 1, and improves by one precisely when 2α is an integer.
Source: §1 · pp. 1–2Takeaways & Limitations
The strict bound supplies smaller candidate cut families for flexible connectivity, multiple safety tiers, motif cuts, and reliability applications.
Source: §4 · p. 5
Abstract
from arXiv · showhide
Let $\lambda$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $\alpha>1$, we prove that there are $O(n^{\lceil2\alpha\rceil-1})$ cuts of size strictly below $\alpha\lambda$. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.
1 Introduction
The paper proves the strict version of the cut-count bound, resolving an open problem posed by Henzinger and Williamson and Karger. Its exponent is sharp, improves by one when 2α is an integer, and the proof extends a recurrence using nested-family bounds and splitting off.
1 Introduction
- The strict cut-count bound resolves an open problem posed by Henzinger and Williamson and Karger.Source: §1 · p. 1
- The exponent improves by one precisely when 2α is an integer, and the improvement applies to path TSP, network-design LP separation, and reliability.Source: §1 · p. 1
- Earlier work bounded cuts below 3λ/2 by O(n^2) using a recurrence over two terminals.Nagamochi et al.’s exact bound at the 4λ/3 threshold fails at equality, as K4 has fourteen qualifying sets where the bound would allow twelve.Source: §1 · pp. 1–2
- The proof extends the recurrence to any fixed number of terminals, bounding nested and pairwise incomparable set families using vertex sampling, then splitting off other vertices and applying Theorem 1.Source: §1 · p. 2
- The exponent is sharp for every fixed α > 1, as shown by Henzinger and Williamson’s parallel-path construction.Source: §1 · p. 2
2 Preliminaries
The preliminaries define the cut and connectivity quantities used in the proof and establish a refined splitting-off operation. This operation preserves local edge connectivities outside the removed vertex while keeping the induced graph on the specified set unchanged.
2 Preliminaries
- For disjoint vertex sets A and B, w(A, B) counts edges between them; the proof uses unweighted multigraphs with loops discarded.The section also defines the minimum cut value and local edge connectivity, and states a cut inequality whose displayed form is not included in the supplied passage.Source: §2 · p. 2
- Splitting off replaces two edges ux and xv with uv; a complete splitting off pairs all edges incident to x and deletes x.Source: §2 · p. 2
- When wG(x, S) < cG(x)/2, the refined operation yields an Eulerian graph preserving G[S] and every local edge connectivity among remaining vertices.The operation requires a connected Eulerian multigraph with at least three vertices and S ⊊ V \ {x}.Source: §2 · p. 2
- Pairing each edge from x to S with a compatible edge leading outside S preserves local connectivities, after which remaining edges at x can be split off outside S.The proof states that each edge at x has at least c(x)/2 other incident edges with which it can be split while preserving those connectivities.Source: §2 · p. 2
3 Proof of the main theorem
The proof reduces cut counting to families of sets satisfying simultaneous cut constraints, then bounds those families through terminal-ordering induction, splitting off, and chain/antichain analysis.
3 Proof of the main theorem
- Setting q=⌈2α⌉−1 and t=(q+1)λ/2 defines the threshold and family F used to prove the theorem.F contains sets X for which c(X∪A)<t for every A⊆S.Source: §3 · p. 3
Case p < q
- Choosing a minimum-adjacency vertex and splitting it off preserves minimum cut at least λ while reducing the graph by one vertex.The extended family on the smaller graph has one more terminal.Source: §3 · p. 3
Case p = q
- For p=q, Mirsky’s theorem bounds |F| by the product of maximum chain and antichain sizes; chains have length at most 2q.The chain bound follows by considering the boundary edges of nested sets and the constraints on their cuts.Source: §3 · pp. 3–4
- For a ≥ 3, ℓ = ⌈6(q + 1) log a⌉ independent weighted samples make X ∩ Q distinct for every X ∈ A; splitting vertices outside Q and applying Theorem 1 yields a = O(1), and the chain bound gives f(n, q) = O(1).Source: §3 · p. 4
Case p < q
- Induction over n and terminal length reduces p<q to a smaller graph, with binomial summation yielding f(n,p)≤γn^(q−p).The induction is simultaneous for all p; the case p=0 proves the theorem because αλ≤t.Source: §3 · pp. 3–4
4 Applications
The theorem sharpens cut-count bounds used in several optimization and reliability applications. Across these settings, it reduces candidate-cut counts or dynamic-program sizes while retaining the stated per-cut checks or approximation guarantees.
Fixed-budget cuts
- O(n^(2d−1)) optimal cuts suffice for fixed-budget minimization with d criteria and d−1 budgets.This recovers the cubic single-budget bound by an alternative proof.Source: §4 · p. 4
Connectivity interdiction
Path TSP
- O(n^3) cuts instead of O(n^4) yield O(n^4) dynamic-program states and O(n^8) LP subproblems, versus O(n^5) and O(n^10) [21].These bounds apply to the path-TSP enumeration after adding a unit-capacity st edge.Source: §4 · pp. 4–5
Flexible graph connectivity
- O(n^3) candidate cuts instead of O(n^4) suffice for flexible graph connectivity separation, uniformly in p and q [6, 13].The remaining violations have capacity strictly below 2p(p+q).Source: §4 · p. 5
Connectivity with several safety tiers
Capacitated network design
- O(n^3) candidate cuts instead of O(n^4) preserve the O(log n) approximation guarantee for capacitated network design.The checks are restricted to cuts below 2ρ because the rounding analysis covers equality at 2ρ.Source: §4 · p. 5
Motif cuts
Network reliability
- For fixed δ>2, choosing α=2 retains O(n^3) reliability cuts with relative error O(n^(2−δ)).More generally, the stated error bound is O(n^(2−(α−1)δ)).Source: §4 · p. 5