PaperlayerView exact revision on arXiv

Source-linked AI summary

Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications

Keerti Choudhary, Amit Kumar, Lakshay Saggi

arXiv:2609.01283v1cs.DS

TL;DR

Structural optimization sensitivity oracles were largely limited to one or two failures, leaving arbitrary updates unsupported across flows, cuts, matchings, and related problems. The paper develops an algebraic framework based on matroid packing, covering, and parity, then applies it to these problems and introduces a localized-update model. It obtains arbitrary-f oracles across the problem family, including exact max-flow and directed min-cut, while subset sensitivity achieves near-optimal dependence on the susceptible-set size.

  • Problem

    Sensitivity oracles for structural optimization problems were generally limited to f≤2 failures, with no efficient f>1 oracles known for several matching, packing, covering, and arboricity problems.

  • Method

    The paper builds an algebraic sensitivity framework for matroid packing, covering, and parity, and decouples updates from matroid representations in the subset sensitivity model.

  • Results

    The framework yields the first arbitrary-f sensitivity oracles across flows, cuts, spanning structures, matchings, and related problems, including exact max-flow, directed min-cut, and subset-model bounds with O~(f^ω) query time and O(fσ^2) space.

  • Takeaways & Limitations

    A common algebraic treatment extends sensitivity-oracle support across a broad class of structural optimization problems, while localized updates permit query time independent of k and matroid density.

  • Takeaways & Limitations

    The general fixed-pair max-flow strategy still has O(f^3ω) query time, motivating the separate subset sensitivity strategy.

Abstract

from arXiv · show

Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$- and global min-cut apply only to undirected graphs; and for matchings, arborescence and spanning-tree packings, and arboricity, no efficient oracle is known for $f>1$. We present a unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids, yielding the first oracles supporting an arbitrary number $f$ of updates across all of these problems (all constructions randomized Monte-Carlo). Concretely, we obtain efficient oracles for exact $(s,t)$-max-flow/min-cut, resolving an open problem of Baswana, Bhanja, and Pandey (ICALP'22) with near-optimal space; for all-pairs $k$-bounded flow, generalizing the near-optimal reachability oracle of Brand and Saranurak (FOCS'19, the case $k=1$); the first oracles for any $f$ for directed $s$- and global min-cut; oracles for $k$-disjoint arborescences, $k$-disjoint spanning trees, colorful spanning trees, and arboricity; and oracles for the existence of an $α$-factor, with perfect matching as the case $α=1$. We further introduce the \emph{subset sensitivity model}, in which updates are confined to a susceptible edge set of size $σ$ fixed during preprocessing. Here we decouple updates from the matroid representation and eliminate the dependence on $k$ and the matroid density altogether: all of the above are supported with $\widetilde O(f^ω)$ query time and $O(fσ^2)$ space. We also prove a matching $Ω(\min\{σ^2,n^2\})$-bit lower bound when $f\ge2$, establishing optimality.

1 Introduction

The paper develops a unified algebraic framework for sensitivity oracles that supports arbitrary updates across structural optimization problems previously limited to one or two failures. It applies matroid packing, covering, and parity primitives to flows, cuts, spanning structures, matchings, and related problems, including a subset model with localized updates.

  • Motivation: Existing sensitivity oracles for structural optimization problems generally support only f≤2 failures, while several matching, packing, covering, and arboricity problems had no efficient oracle for f>1.Directed s- and global min-cut lacked non-trivial oracles entirely, and the arbitrary-f case for fixed-pair min-cut remained open.
  • Framework: The paper introduces an algebraic framework for matroid packing, covering, and parity, replacing problem-specific constructions with reusable sensitivity oracles.The framework is instantiated through problem-specific reductions for a broad range of graph problems.
  • Flows and cuts: Exact fixed-pair max-flow is supported after arbitrary f updates with polynomial dependence on f, near-optimal space, and query bounds independent of the flow value k.The result resolves the open problem of Baswana, Bhanja, and Pandey and improves over bounds exponential in f and dependent on k.
  • Flows and cuts: The framework yields the first arbitrary-f directed s-min-cut and global min-cut oracles, alongside oracles for all-pairs bounded flow and spanning structures.The directed cut oracles use O(f^2 n^3 log n) space and O~(f^(3ω+1)) query time, while an alternate construction offers a space-query trade-off.
  • Subset sensitivity: The subset sensitivity model restricts updates to a fixed susceptible set and removes dependence on k and matroid density at the cost of quadratic dependence on the susceptible-set size.It supports the listed problems with O~(f^ω) query time and O(fσ^2) space, and matching Ω(min{σ^2,n^2})-bit lower bounds establish optimality.

2 Preliminaries

The preliminaries establish the graph, flow, matroid, and algebraic foundations used throughout the sensitivity-oracle framework. They also introduce determinant tools for randomized, update-efficient queries.

  • Graph and flow preliminaries: A trail is an edge sequence with consecutive head-to-tail incidence, while a path additionally forbids repeated vertices.
  • Graph and flow preliminaries: For an (s,t)-pair, λ_G(s,t) is the maximum flow value and the minimum cut has the same value.
  • Graph and flow preliminaries: Residual graphs reverse flow-carrying edges, and the nearest minimum cut is the unique minimum cut whose source side is contained in every other minimum-cut source side.
  • Algebraic primitives: Determinant preprocessing supports sparse updates in near matrix-multiplication query time, with specialized bounds when polynomial degree is zero.The base lemma assumes a nonsingular matrix, while the paper extends it to singular matrices with the same asymptotic bounds.
  • Algebraic primitives: The paper uses Cauchy-Binet, generalized Laplace expansion, and Schwartz-Zippel to expand determinants and obtain high-probability correctness over finite fields.
  • Matroid preliminaries: A linear matroid represents independence through full column rank, while sparse representations bound each column's number of nonzero entries.

3 Matroid Packing and Matroid Covering

This section develops algebraic sensitivity oracles for matroid packing and covering by converting updated independence questions into determinant queries. The resulting general and subset models provide explicit trade-offs among update count, rank, susceptible-set size, and query complexity.

  • Problem formulations: The k-packing problem asks whether k disjoint common bases exist, while k-covering asks whether the ground set partitions into k independent sets.
  • Matroid packing: The framework analyzes intersections of k-fold matroid unions to represent packing feasibility algebraically.Randomized union representations preserve dependence deterministically and preserve independence with high probability.
  • Matroid packing: The determinant construction encodes common bases, and the minimum Y-degree identifies the minimum-weight common basis with high probability.
  • General sensitivity: O((k^2δ)^ω) query time supports decision k-packing after δ updates, with O(km + (kr)^2 log(kr)) space.
  • General sensitivity: The weighted packing oracle returns the exact minimum weight with query time eO(W·kr·(k^2δ)^ω) and space O(km + W(kr)^3 log(kr)).
  • Subset sensitivity: Subset sensitivity reduces decision query time to O(f^ω) and space to O(σ^2), while weighted queries use eO(W·kr·f^ω) time and eO(W·kr·σ^2) space.When σ is much smaller than m and k is large relative to f, this model can improve both space and query time.
  • Matroid covering: Matroid covering is decided by determinant nonzeroness, yielding general sensitivity with O((δk)^ω) query time and subset sensitivity with O(f^ω) query time.The subset construction maintains exactly kr active columns while updates toggle susceptible elements and switch entries.

4 Max-Flows, Min-Cuts, 𝑠-Min-Cuts, Global Min-Cut

The paper reduces bounded flow and cut queries to sensitivity oracles for matroid packing, using auxiliary graphs and sparse algebraic updates. This yields randomized oracles for arbitrary update counts in directed graphs, including all-pairs bounded flow, nearest min-cuts, s-min-cuts, and global min-cuts.

  • Matroid formulation: A k-packing of common bases in two partition matroids is equivalent to finding λ edge-disjoint paths between designated source and sink vertices.The auxiliary construction uses self-loops and parallel edges to complete paths into common bases.
  • Query reduction: δ = O(fk^2) entries capture the additive packing-Laplacian update caused by f graph updates and query-specific auxiliary edges.The auxiliary parallel edges and self-loops contribute O(k^2) entries, while the f updates contribute the remaining terms.
  • All-pairs bounded flow: O((fk^2)^ω log k) query time returns min(k, λ_G+U(s,t)) for all-pairs bounded flow.The oracle binary-searches the flow value and evaluates O(log k) updated Laplacians.
  • Nearest min-cut: O((fk^2)^ω n) query time identifies the nearest (s,t)-min-cut after f updates.The source side is obtained through n auxiliary flow queries, each preserving the O(fk^2) update size.
  • s-min-cut and global min-cut: O(f^2n^3 log n) space and Õ(f^(3ω+1)) query time support directed s-min-cut and global min-cut for arbitrary f.The corresponding cut partition is reported in Õ(f^(3ω)n) time.

5 Arborescences, Spanning Trees, Colorful Spanning Trees, Arboricity

The framework extends matroid packing and covering sensitivity oracles to arborescences, spanning trees, colorful spanning trees, and arboricity. These constructions support arbitrary update counts with algebraic query bounds, including O(f^ω) for colorful spanning trees.

  • Arborescences: k-disjoint rooted arborescences are formulated as k-packings of common bases in a graphic matroid and a partition matroid.The graphic matroid enforces acyclicity, while the partition matroid enforces at most one incoming edge per non-root vertex.
  • Arborescences: O((fk^2)^ω) query time decides whether k-disjoint rooted arborescences exist, while weighted queries return their minimum total cost.The weighted query time is Õ(Wkn·(fk^2)^ω).
  • Spanning trees: O((fk^2)^ω) query time decides whether an updated undirected graph contains k edge-disjoint spanning trees.The weighted oracle returns the minimum total cost of such k spanning trees in Õ(Wkn(fk^2)^ω) time.
  • Colorful spanning trees: O(f^ω) query time decides whether an updated colored graph has a colorful spanning tree, using O(n^2 log n) space.The oracle supports edge insertions, deletions, and color changes.
  • Arboricity: O((kf)^ω) query time decides whether the updated graph partitions into k forests, under the condition m_curr ≤ k(n−1).This is the arboricity decision oracle based on matroid covering.

6 Sensitivity Oracles for Matroid Parity

For linear matroid parity, the paper uses a determinant and Pfaffian representation that enumerates parity bases and exposes their weights algebraically. Randomized sensitivity oracles then support arbitrary pair updates for both decision and exact weighted queries.

  • Problem formulation: Matroid parity selects r/2 pairs whose 2(r/2) elements form a basis of an even-rank linear matroid.The selected pairs constitute a parity basis, and the weighted problem minimizes their total pair weight.
  • Algebraic formulation: The determinant of the parity Laplacian enumerates parity bases, and its minimum Y-degree minus rW equals twice the minimum parity-basis weight.The determinant is the square of a Pfaffian, whose terms correspond to valid pair selections.
  • Decision oracle: O((c^2f)^ω) query time decides whether a parity basis exists after f pair updates.The oracle uses O(c^2m + r^ω) preprocessing time and O(r^2 log r) space.
  • Weighted oracle: Õ(Wr(c^2f)^ω) query time returns the exact minimum weight of a parity basis after f pair updates.The weighted oracle uses Õ(c^2m + Wr^3) preprocessing time and O(Wr^3 log r) space.

7 𝛼-Factors and Matchings

The paper reduces α-factor existence and optimization to linear matroid parity, then builds sensitivity oracles for bounded and arbitrary degree constraints. These yield randomized oracles for arbitrary update counts, including perfect matching as α=1.

  • An α-factor is a spanning subgraph giving every vertex v exactly α(v) incident edges, with minimum-cost variants minimizing total edge cost.
  • Algebraic reduction: An α-factor exists if and only if the associated linear matroid admits a parity base, with a bijection between α-factors and parity bases.
  • Algebraic reduction: The minimum-cost α-factor has the same cost as the minimum-weight parity basis of the constructed matroid.
  • Arbitrary degrees: For arbitrary degree bounds, an auxiliary graph reduces each update to O(f) changes while preserving α-factor existence and minimum cost.
  • Bounded degrees: For degree bounds α(v)≤k, the existence oracle uses O((kn)^2 log n) space and O(f^ω k^(2ω)) query time.

8 Subset Sensitivity Oracles

The subset sensitivity model restricts updates to a fixed susceptible edge set and applies matroid packing reductions to flow and cut problems. This produces compact randomized oracles for bounded flows, distances, s-min-cut, and global min-cut under confined updates.

  • Flow oracles: Subset flow queries restrict source and sink vertices to V_Q and updates to a fixed susceptible edge set E_Q of size σ.
  • Flow oracles: All-pairs bounded flow supports λ*=min(k, λ_{G+U}(s,t)) with O(σ^2) space and O((f+k)^ω log k) query time.
  • Cut oracles: The corresponding nearest min-cut oracle uses O((σ+n|V_Q|)^2) space and O((f+k)^ω n) query time.
  • Reachability and distance: Setting k=1 reduces bounded-flow decision to reachability and min-cost flow to distance sensitivity after f edge updates.
  • Cut oracles: For fixed-source directed graphs, subset s-min-cut and global min-cut value oracles use O(σ^3) space and approximately O(f^(ω+1)) query time.

8.2 Subset Sensitivity for Spanning Structures

The subset framework extends to arborescences, spanning trees, colorful spanning trees, and arboricity by replacing general matroid oracles with subset versions. Fixed-root cut-value queries achieve especially compact bounds independent of the packing parameter k.

  • Arborescences: Dynamic-root arborescence queries use O(σ^2) space and O((f+k)^ω) query time for k-disjoint rooted arborescences.
  • Fixed-root cuts: Fixed-root s-min-cut and global min-cut values use O(fσ^2) space and approximately O(f^ω) query time.
  • Fixed-root cuts: The fixed-root approach improves query time from approximately O(f^(ω+1)) to approximately O(f^ω) for cut values, while cut partitions still require the nearest-min-cut approach.
  • Spanning trees: For k edge-disjoint spanning trees, subset queries use O(σ^2) space and O(f^ω) query time.
  • Colorful trees and arboricity: Colorful spanning-tree existence uses O(σ^2) space and O(f^ω) query time, while arboricity queries use O(σ^2) space and exactly O(f^ω) operations.

8.3 Subset Sensitivity for Matroid Parity

The paper applies subset sensitivity determinant techniques to linear matroid parity and then lifts them to α-factors. Pair updates affect only a constant number of diagonal entries, enabling query bounds that depend on f and σ rather than the full matroid representation.

  • Matroid parity: The LMP matrix is factorized into augmented representation matrices and a block-diagonal matrix, allowing subset determinant data structures to maintain parity queries.
  • Matroid parity: Each updated pair changes two diagonal entries, so f pair updates become at most 2f diagonal modifications.
  • Matroid parity: The decision parity oracle uses O(σ^2) space and O(f^ω) query time, while the weighted oracle uses approximately O(Wrσ^2) space and approximately O(Wrf^ω) query time.
  • α-factors: For k-bounded α-factors, subset existence queries use O(σ^2) space and O(f^ω) query time.
  • α-factors: For arbitrary degree bounds, the auxiliary graph has dimension O(nf), degree bounds at most 2f, and preserves α-factor existence and cost under the reduction.
  • α-factors: Arbitrary-degree α-factor existence uses O(σ^2) space and O(f^ω) query time, while minimum-cost queries use approximately O(Wnf^(ω+1)) query time.

9 Lower Bounds

The section proves quadratic subset-sensitivity space lower bounds for flows, cuts, colorful spanning trees, and matching under two updates. Each reduction encodes a Boolean matrix whose entries are recoverable from oracle answers.

  • Flows and Cuts: Ω(min{σ^2, n^2}) bits are necessary for bounded flow and global directed min-cut subset sensitivity oracles under f=2 updates.The construction uses a unique candidate path whose existence encodes each matrix entry.
  • Flows and Cuts: Each two-edge update makes the bounded flow and minimum-cut value equal to the corresponding Boolean matrix entry.The inserted edges create an (s,t)-path exactly when the encoded matrix edge exists.
  • Colorful Spanning Trees: Ω(min{σ^2, n^2}) bits are required for colorful spanning tree subset sensitivity under f=2 updates.A colorful spanning tree exists after the query if and only if the targeted matrix entry is one.
  • Bipartite Matching: Ω(min{σ^2, n^2}) bits are required for maximum bipartite matching subset sensitivity under f=2 updates.Deleting two matching edges isolates two vertices, and the updated matching has size 2p−1 exactly when the targeted matrix entry is one.

A.1 Subset Sensitivity Oracle for Matrix Determinant

The subset determinant oracle freezes the matrix representation and handles susceptible updates through diagonal changes, reducing each query to a small determinant computation. In the scalar case, it uses O(σ^2) space and O(f^ω) query time.

  • Subset Sensitivity Model: Updates confined to a susceptible set Q modify only diagonal entries of D while A and B remain fixed during preprocessing.Each susceptible element can be toggled, removed, or reweighted without changing the matroid representation.
  • Complexity: O(σ^2) space and O(f^ω) query time hold when A and B have scalar-field entries.Preprocessing takes O(σ^2r^{ω−2}+r^ω) operations.
  • Complexity: For polynomial entries, space becomes Õ(drσ^2) and query time becomes Õ(drf^ω).The polynomial-degree parameter scales both storage and determinant evaluation.
  • Query Algorithm: The query extracts an (f+δ)×(f+δ) submatrix, applies the update matrix, adds the identity, and evaluates its determinant.The relevant submatrix is retrieved from the precomputed susceptible-set matrix W_Q.

A.2 Extension of Theorem 2.4 to General matrices

The general-matrix extension applies the same susceptible-set determinant strategy to arbitrary modification matrices supported on Q×Q. It uses a low-rank factorization of each update and evaluates a determinant whose dimension depends on the number of changed entries.

  • General Updates: A modification matrix supported on Q×Q can be decomposed into a low-rank product using only susceptible-set indices.The factorization uses standard basis columns for the nonzero rows and columns of the update.
  • Rank Deficiency: If the base rank deficiency exceeds the update sparsity, every valid updated determinant is zero and queries answer in O(1) time.The algorithm detects this condition during preprocessing with a short-circuit flag.
  • Complexity: For scalar matrices, the general oracle uses O(σ^2) space and O(δ_C^ω) query time.The query determinant has dimension O(δ_C)×O(δ_C).
  • Complexity: For polynomial matrices, storage is Õ(dNσ^2) and query time is Õ(dNδ_C^ω).The inverse and extracted susceptible-set submatrix have polynomially bounded rational degree.

A.3 Proof of Theorem 3.2

The proof represents a k-fold matroid union by stacking independently scaled copies of a representation matrix. Random diagonal scaling makes independence equivalent, with high probability, to full column rank after evaluation.

  • Representation: The k-fold union representation stacks k copies of A, each scaled column-wise by an independent random diagonal matrix.This construction encodes partitions of a set among the k matroid copies.
  • Independence Characterization: A set is independent in the union exactly when a corresponding maximal minor is a nonzero polynomial.The proof selects independent row subsets from each partition block.
  • Polynomial Argument: Distinct partitions contribute linearly independent monomials, so one independent partition makes the determinant polynomial nonzero.The coefficient is a product of nonzero minors from the constituent matroid representation.
  • Randomization: Random evaluation preserves independence with high probability, while dependent sets remain deterministically dependent.The Schwartz–Zippel lemma provides the randomized correctness guarantee.

A.4 Extension of Perfect 𝛼-factor Sensitivity Oracle to Maximum 𝛼-factor

The section extends perfect α-factor sensitivity oracles to maximum α-factors by reducing maximum-factor queries to perfect β-factor queries on an auxiliary graph. The reduction preserves both factor cardinality and minimum cost, yielding sensitivity and subset-sensitivity oracles with explicit space and query bounds.

  • Auxiliary reduction: Maximum α-factor sensitivity is reduced to perfect β-factor sensitivity through an auxiliary graph with three dummy vertices and zero-cost edges.The construction adds deficiency- and f-dependent parallel edges, triangle edges, and β degree requirements while preserving the initial minimum-cost solution.
  • Update mapping: The reduction parameterizes each update by i∈[−f, f] using additional dummy-edge insertions and deletions that encode changes in factor cardinality.For i>0, edges are added incident to z1 and removed between z2 and z3; the complementary operation applies for i≤0.
  • Equivalence: The maximum α-factor size equals |M| + i*, where i* is the largest i in [−f, f] for which the updated auxiliary graph admits a perfect β-factor.The corresponding minimum-cost perfect β-factor also has the same cost as the minimum-cost maximum α-factor.
  • Query procedure: A binary search over [−f, f] identifies i*, adding an O(log f) overhead to the perfect β-factor oracle query.The maximum possible i corresponds exactly to the maximum α-factor after the original updates, while zero-cost dummy edges preserve the optimization objective.
  • Oracle bounds: The resulting full-update oracles use O((fn)^2 log n) space and Õ(f^3ω) query time for maximum α-factor size, while minimum-cost queries use Õ(Wn f^(3ω+1)) query time.Subset sensitivity reduces the corresponding space to O(σ^2) for maximum size and Õ(Wfnσ^2) for minimum cost, with query times Õ(f^ω) and Õ(Wn f^(ω+1)), respectively.
Loading 2609.01283v1…