PaperlayerView exact revision on arXiv

Source-linked AI summary

An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions

Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka

arXiv:2609.31290v1cs.DS

TL;DR

All-pairs nearest minimum cuts lacked a compact representation despite their broad applications. The paper encodes them in a linear-space structure, matching Gomory-Hu tree bounds and supporting an all-pairs edge-insertion sensitivity oracle.

  • Problem

    Nearest mincuts have applications including reachability and sensitivity oracles, but an optimal compact representation for all pairs had remained unavailable.

    Source: §1 · p. 3, §11 · p. 30

  • Method

    The paper encodes every pair’s nearest mincut in an O(n)-space structure that reports a queried cut in O(n) time.

    Source: §1 · p. 4

  • Results

    The all-pairs nearest-mincut representation uses O(n) space and answers queries in worst-case O(n) time, matching Gomory-Hu tree bounds.

    Source: §1 · p. 4, §11 · p. 30

  • Takeaways & Limitations

    The nearest-mincut structure yields an O(n)-space insertion sensitivity oracle that tests whether an edge insertion increases a pair’s mincut value.

    Source: §1 · p. 5

    Improving construction time remains an open objective; the authors suggest O(n polylog n) maxflow computations may suffice and seek polylog n computations.

    Source: §11 · p. 30

Abstract

from arXiv · show

Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every $s,t\in V$ using just $O(n)$ space. In this work, we ask whether the same compactness is achievable for the natural and structured family of all-pairs \textit{nearest minimum cuts}. The nearest minimum $(s,t)$-cut is the unique inclusion-wise minimal one among all minimum $s,t$-cuts containing $s$. This family has proven useful in a wide range of applications, including fault-tolerant reachability, minimum cut sensitivity oracles, cactus representations, and fast Gomory-Hu tree constructions. Despite its fundamental role, no subquadratic space representation is known for them to date. The $O(n)$ space representations are known only in single-source settings, where given a source $s$, one can report the nearest minimum $(t,s)$-cut for any $t\in V\setminus \{s\}$. We close this gap by presenting the first optimal space representation of all-pairs nearest minimum cuts, providing a natural analogue of the Gomory-Hu tree. Our main result is an $O(n)$ space structure that encodes the nearest minimum cut between every pair of vertices. Furthermore, given any pair $s,t\in V$, it can report the nearest minimum $s,t$-cut in $O(n)$ time. Both bounds match those of the Gomory-Hu tree and are worst-case optimal. As an application, we design an all-pairs minimum cut sensitivity oracle for edge insertion: a data structure that occupies $O(n)$ space and, given any edge $e$, can determine for all pairs $s,t\in V$ whether the minimum $s,t$-cut value increases upon insertion of $e$ in $O(n^2)$ total time. Existing insertion sensitivity oracles were either limited to the single-source setting or used $O(n^2)$ space for all-pairs [Baswana, Gupta, and Knollmann, Algorithmica'22; Baswana and Pandey, SODA'22].

1 Introduction

The introduction asks whether all-pairs nearest minimum cuts can have a compact representation like a Gomory-Hu tree. It presents a linear-space hierarchy and uses it to obtain insertion-sensitivity results for all pairs.

1 Introduction

  • Nearest cuts are canonical: Near(u, v) is the residual-graph region reachable from u after a u,v maximum flow, and they appear in several graph applications.The cited applications include fault-tolerant reachability, mincut sensitivity, cactus representations, and Gomory-Hu tree construction.Source: §1 · p. 3
  • The compact all-pairs result extends beyond existing single-source representations, while a straightforward extension using minimal Gomory-Hu trees would require Ω(n) distinct trees in the worst case.Existing all-pairs insertion structures use O(n^2) space; known compact nearest- and farthest-cut representations are for a fixed source.Source: §1 · pp. 3–5
  • The Nearest Mincut Hierarchy stores every all-pairs nearest cut in O(n) space and reports a queried cut in worst-case O(n) time.These bounds match the Gomory-Hu tree while representing nearest rather than arbitrary minimum cuts.Source: §1 · pp. 3–4
  • For an inserted edge, a pair's mincut value increases exactly when the edge lies between Near(u, v) and Near(v, u); the resulting oracle uses O(n) space and O(n) query time.The work generalizes a single-source insertion oracle to all pairs while retaining its space and query-time guarantees.Source: §1 · p. 5
  • Further space improvements face lower bounds: even two unit-capacity insertions in a fixed source-sink setting require Ω(n^2) bits.For polynomial-weight query edges, reporting the new mincut capacity requires Ω(n^2 log n) bits, even in the single-source setting.Source: §1 · p. 5
  • The structure can also report all affected pairs in O(n^2) total time, using O(n) space and amortized O(1) time per pair.The introduction relates this result to reporting a source's nearest-mincut tree in O(n) time.Source: §1 · pp. 5–6

2 Preliminaries

The preliminaries establish cut notation and structural cut properties, then introduce the Connectivity Carcass interface that represents laminar terminal partitions in a tree and connects them to nearest mincuts.

2 Preliminaries

  • For an undirected, positively weighted connected graph, cut capacity sums the weights of crossing edges; Steiner mincuts separate a specified terminal set.The notation also defines capacities and mincut values for terminal pairs and sets.Source: §2 · p. 6
  • Submodularity and posimodularity imply that suitable intersections, unions, and set differences of minimum cuts remain minimum cuts.The four component lemma supplies an additional inequality among capacities of three sets and their disjoint regions.Source: §2 · p. 6

Key Elements of the Connectivity Carcass

  • The Connectivity Carcass organizes terminals by whether Steiner mincuts separate them and represents valid terminal partitions through its skeleton interface.A valid partition is induced on the terminals by a Steiner mincut; it distinguishes a vertex when minimum cuts can place that vertex on either side.Source: Key Elements of the Connectivity Carcass · p. 7
  • The carcass skeleton is an O(d(S))-node tree whose edges encode laminar valid terminal partitions; each vertex projects to a path marking partitions that distinguish it.When a projection lies wholly on one side of a skeleton edge, every corresponding minimum cut keeps the vertex with that side's terminals.Source: Key Elements of the Connectivity Carcass · p. 7
  • For non-equivalent terminals s and t, Near(s,t) induces a laminar valid partition represented by the unique skeleton edge from s toward t.This connects directional nearest mincuts to the carcass tree structure.Source: Key Elements of the Connectivity Carcass · p. 7

3 Technical Overview

The overview presents a linear-space hierarchy for storing all nearest mincuts and explains how it supports O(n)-time reporting. Its query grows Near(x,y) from the LCAT of x and y up the hierarchy, using projections and chain maximizers to classify vertices.

3.1 The Nearest Mincut Hierarchy

  • The nearest mincut hierarchy occupies O(n) space and reports Near(x,y) in O(n) time for any ordered vertex pair.It augments the skeleton hierarchy with O(n) stored projections and chain maximizers, plus LCA and level-ancestor structures.Source: §3.1 · pp. 8–9

3 Technical Overview

  • Queries begin at LCAT(x,y), determine the cut's intersection with that node from its skeleton, then expand the known intersection toward the root.Each step extends the known Near(x,y) intersection from one hierarchy node to its parent.Source: §3.1 · p. 9

3.3 The First Step : Parent of LCAT (𝑥, 𝑦)

  • For the first expansion, sibling groups within each parent skeleton are wholly inside or outside Near(x,y), so one representative projection per subtree suffices to classify them.Subtrees partition the siblings, reducing the need to store projections for every sibling pair.Source: §3.3 · pp. 9–10

3.4 The Generic Steps : Any ancestor of LCAT (𝑥, 𝑦)

  • In generic steps, case (III) can leave a vertex's membership ambiguous; the relevant cuts form a containment chain, whose maximal cut is represented by a pair of witness vertices.That chain maximizer lets the query test whether Near(x,y) belongs to the chain without storing all its cuts.Source: §3.4 · pp. 11–13

4 Chain Maximizers for a Family of Nearest Mincuts

The section establishes that, for a vertex’s projected subtrees, the relevant families of nearest mincuts form chains under containment and each nonempty family has a unique maximal element. A crossing-mincut lemma supports this structural result.

Chain Maximizers

  • Each nonempty family of nearest mincuts associated with the two projected subtrees is nested by containment and has a unique inclusion-wise maximal element.The families are defined using cuts Near(a,b) that contain the corresponding subtree and exclude v.Source: §4 · pp. 14–15

All-Pairs Crossing Mincuts Lemma

  • The crossing-mincut lemma supplies a structural result used to prove the chain property for nearest mincuts.The section introduces the crossing result as a step toward the main technical result for the chain.Source: §4 · pp. 14–15
  • For the specified crossing configuration, C\C′ is an (a′,b′)-mincut and C′\C is a (b′,a′)-mincut.The proof establishes equality of the crossing cuts’ capacities and of the capacities of their intersection, union, and differences.Source: §4 · p. 15

5 Data Structure: Nearest Mincut Hierarchy

The nearest mincut hierarchy augments a skeleton hierarchy with vertex projections and chain maximizers to support pair queries. Its total space, including the tree-query augmentations, is O(n).

Nearest Mincut Hierarchy

  • The skeleton hierarchy is augmented with vertex projections and chain maximizers to form the nearest mincut hierarchy.The hierarchy starts from the tree T and skeletons Hμ, and adds these stored components for query support.Source: §5 · p. 16

Vertex Projections

  • For each μ-subtree, the structure selects a representative and stores its projection, following it down the hierarchy when it is a single nonempty node.Otherwise, it stores the projection’s endpoints, or its single endpoint for an empty node.Source: §5 · p. 17

Chain Maximizers

  • For each stored projection, the structure stores two chain maximizers, represented by vertex pairs for the maximal nearest mincuts in the two associated families.The maximizers are stored alongside the representative’s projection.Source: §5 · p. 17

Space Guarantees

  • The hierarchy and its LCA and level-ancestor augmentations occupy O(n) space.The skeleton hierarchy uses O(n) space, and augmenting it with these tree data structures preserves that bound.Source: §5 · p. 17
  • The number of stored projections is O(n), so the projections and their constant-space chain maximizers also use O(n) space overall.Each skeleton Hν stores O(|Hν|) projections, and the sum of skeleton sizes is O(n).Source: §5 · pp. 17–18

6 A Characterization of Skeleton Subtrees

The subtree characterization determines membership in Near(x,y) for vertices projected in a skeleton, under the stated hierarchy and subtree conditions. Its cases distinguish projections with two in-edges, an out-edge, or exactly one in-edge.

Purpose

  • The characterization supports the pair-query algorithm and the design of sensitivity oracles.The section identifies both uses for its structural result.Source: §6 · p. 18

Case II

  • If an endpoint of πμ(v) lies in an out-α-subtree, then v does not belong to Near(x,y).The theorem’s case applies when at least one endpoint is in an out-α-subtree.Source: §6 · p. 18

Case III

  • With exactly one in-edge of α, v belongs to Near(x,y) if z is in Near(x,y); otherwise, membership holds exactly when x is not in Near(w,z).Here w and z are the stored chain maximizers for the relevant in-α-subtree and projection endpoint.Source: §6 · pp. 18–19

Case I

  • When πμ(v) contains two in-edges of α, v belongs to Near(x,y).This is the two-in-edge case of the characterization.Source: §6 · p. 18

7 Algorithm for Reporting the Nearest Mincut for a Pair of Vertices

The algorithm reports Near(x,y) by ascending the nearest mincut hierarchy and extending the known cut across successive hierarchy nodes. It classifies subtrees using representatives, yielding an O(n)-time query.

7.1 Query Algorithm

  • Starting at LCAT(x,y), the query ascends the hierarchy tree while maintaining Near(x,y) intersected with the current node.At each level it uses the skeletons, projections, and chain maximizers to determine the next intersection.Source: §7.1 · pp. 19–20

7.2 Correctness

  • Each subtree is wholly contained in Near(x,y) or disjoint from it, so classifying its representative determines the subtree’s membership.The classification uses stored projections and chain maximizers, with constant-time tests for the characterization’s cases.Source: §7.2 · pp. 20–21
  • When {w,z}∩Near(x,y)={w}, LCAT(x,y) is a descendant of LCAT(w,z), enabling the needed membership test through a skeleton LCA query.The proof uses this hierarchy relation to locate the node where x’s membership in Near(w,z) can be tested.Source: §7.2 · p. 21
  • The complete algorithm reports Near(x,y) in O(n) time by processing the successive hierarchy levels and extending the cut across newly added vertices.The total work is O(n) because the sizes of the successive differences sum to O(n).Source: §7.2 · pp. 21–22

8 Reporting the Nearest Mincut Tree of a Vertex

Given a nearest mincut hierarchy and source vertex, the algorithm constructs that source’s nearest mincut tree in O(n) time. It builds the tree incrementally along the hierarchy, attaching local trees at identified attachment nodes.

8 Reporting the Nearest Mincut Tree of a Vertex

  • O(n) time suffices to construct a source’s nearest mincut tree from the hierarchy.The algorithm maintains a dynamic LCA oracle as it inserts nodes.Source: §8 · pp. 22, 25
  • The source tree’s nodes are exactly the relevant children along the hierarchy path, and each local tree preserves the corresponding nearest-cut structure.For vertices newly added at a hierarchy level, their nearest cuts to the source equal their nearest cuts to the preceding hierarchy node.Source: §8 · pp. 22–23
  • At each hierarchy step, the algorithm builds a local tree and attaches its subtrees to the partial tree at their attachment nodes.Each representative terminal’s attachment node is found in O(1) time.Source: §8 · pp. 24–25
  • The attachment routine uses the projection’s position relative to the preceding hierarchy node to determine the attachment node.The cases are a projection contained in one subtree, meeting two incident edges, or meeting one incident edge; the routine uses LCA queries and, in the single-edge case, chain maximizers.Source: §8 · pp. 25–27, Figure 6 · p. 26

9 Sensitivity Oracles for the Insertion of an Edge

The section applies the nearest mincut hierarchy to edge-insertion sensitivity queries. It gives an O(n) single-pair query and an O(n^2) total-time all-pairs procedure.

Single-pair query

  • O(n) time answers whether inserting an edge increases a specified pair’s mincut value.The query reports both oriented nearest cuts and checks whether the inserted edge’s endpoints lie on opposite sides in the required orientation.Source: §9 · p. 28
  • For integral graphs and a unit-weight inserted edge, the hierarchy can also report one mincut in the updated graph.At least one of the two oriented nearest mincuts remains a mincut after insertion.Source: §9 · p. 28

All-pairs query

  • O(n^2 + k) total time reports all k vertex pairs whose mincut value increases after an edge insertion.The procedure constructs a nearest mincut tree for each source, then applies the all-pairs reporting result of.Source: §9 · p. 28

10 Minimal Gomory-Hu Tree Lower Bound

Some graphs require Ω(n) minimal Gomory-Hu trees to encode all-pairs nearest mincuts. The lower bound follows from cuts that each appear in only one such tree.

10 Minimal Gomory-Hu Tree Lower Bound

  • Ω(n) minimal Gomory-Hu trees can be necessary to encode all-pairs nearest mincuts.The constructed graph has n distinct cuts, each captured by a different minimal Gomory-Hu tree.Source: §10 · p. 29
  • In the construction, each cut Near(b_i, c_i) is represented only by a minimal Gomory-Hu tree rooted at c_i or d_i.The proof uses 4n vertices arranged as a weighted line and n attached triangles.Source: §10 · p. 29

11 Conclusion and Future Works

The paper presents an O(n)-space representation of all-pairs nearest and farthest mincuts with O(n)-time queries, alongside an all-pairs insertion sensitivity oracle. It also identifies open directions and discloses the authors’ use of AI tools.

11 Conclusion and Future Works

  • The all-pairs nearest and farthest mincut representation uses O(n) space and supports O(n)-time queries.The paper presents it as matching the classical Gomory-Hu tree’s bounds while representing a richer cut family.Source: §11 · p. 30
  • The work highlights chain structure in the representation and suggests the connectivity carcass may be useful for other cut problems.The latter suggestion is made in conjunction with recent work [BPP26].Source: §11 · p. 30
  • All-pairs edge-deletion sensitivity remains open; existing oracles use O(min{n^2, m}) space or restrict O(n)-space support to single-source queries.The authors propose the nearest mincut hierarchy as a possible starting point.Source: §11 · p. 30
  • The insertion oracle’s O(n)-time pair query is not optimal for decision queries; O(1) queries are known with O(n^2) space.The open question is whether sublinear query time can be achieved with O(n) space.Source: §11 · p. 30
  • Faster construction remains an objective: O(n polylog n) maxflow computations seem plausible, while polylog n is desired.The latter would match fast Gomory-Hu construction bounds such as.Source: §11 · p. 30

AI Disclosure

  • The authors used GitHub Copilot for inline writing suggestions and Claude for feedback on Sections 7 and 8.They state that the proof ideas and technical content were developed by the authors.Source: AI Disclosure · p. 30

A Missing Proofs

The appendix establishes an uncrossing property for minimum cuts using submodularity, then uses it to rule out certain separating minimum cuts based on LCAT relationships.

A Missing Proofs

  • Submodularity forces the two cuts formed from the intersection and union of an S-mincut and a T-mincut to remain minimum cuts.Each original cut has capacity no greater than its corresponding S-cut or T-cut among the intersection and union; submodularity makes both inequalities equalities.Source: A Missing Proofs · p. 33
  • When LCAT(α, β) is neither α nor β, no u,v-mincut can separate u′ from v′.The proof assumes such a cut exists and combines it with a μ-mincut using intersection and union; uncrossing would produce a μ-mincut separating vertices in the same μ-equivalence class, a contradiction.Source: A Missing Proofs · p. 34
  • The contradiction relies on a μ-mincut containing both endpoint pairs because α and β lie in distinct μ-equivalence classes.Intersecting with the assumed u,v-cut separates u and v, while taking the union separates u′ and v′.Source: A Missing Proofs · p. 34
Loading 2609.31290v1…