MathDB

Baswana–Bhanja–Pandey open problem on dynamic exact flow/min-cut sensitivity oracles

Given a directed graph GG, vertices s,t∈V(G)s,t\in V(G), and an integer f≥1f\ge 1, construct a sensitivity oracle that, after preprocessing GG, answers exactly for every set UU of at most ff edge insertions and deletions the value of maxflow⁡G⊕U(s,t)\operatorname{maxflow}_{G\oplus U}(s,t), equivalently mincut⁡G⊕U(s,t)\operatorname{mincut}_{G\oplus U}(s,t), without recomputing the optimization problem from scratch. The goal is an efficient oracle with compact, preferably near-optimal, space usage and efficient query time, for arbitrary ff.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Exact (s,t)(s,t)-min-cut sensitivity oracle

    Preprocess a directed graph GG so that, after any set of at most ff edge insertions and deletions, the exact value of the minimum ss-tt cut in the resulting graph G⊕UG\oplus U can be queried efficiently using compact space.

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

References

Primary source

arXiv

Additional references

algorithmsgraph-theorymatroid-theory
Posted

Progress summary

Refreshed
Claimed solved

A new unrefereed preprint claims to resolve the problem by giving exact, compact data structures that handle arbitrary updates in several network and matching settings.

The problem concerns exact flow and cut sensitivity oracles that remain usable after arbitrary updates. The cited preprint claims a general framework covering max-flow/min-cut and related packing, covering, and matching problems.

September 2026 claimed oracle framework

On September 1, 2026, the preprint Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications claimed near-optimal-space exact oracles for arbitrary updates, together with a subset-sensitivity model and matching lower bounds. Its applications include directed cut, packing, covering, and matching settings, implying a claimed resolution of the tracked open problem.

Current status (as of September 2026): The preprint claims the exact arbitrary-update oracle problem is resolved in the stated settings, but the claim remains unverified.

Sources

Solutions 0

No solutions have been posted yet.