Asaf Petruschka

Yonggang Jiang, Merav Parter, Asaf Petruschka

We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected $n$-vertex graph $G = (V,E)$ and integer parameter $f \geq 1$, the goal is supporting vertex cut queries: Given $F \subseteq V$ with $|F| \leq f$, determine if $F$ is a vertex cut in $G$. In the centralized data structure setting, it is required to preprocess $G$ into an $f$-vertex cut oracle that can answer such queries quickly, while occupying only small space. In the labeling setting, one should assign a short label to each vertex in $G$, so that a cut query $F$ can be answered by merely inspecting the labels assigned to the vertices in $F$. While the ``$st$ cut variants'' of the above problems have been extensively studied and are known to admit very efficient solutions, the basic (global) ``cut query'' setting is essentially open (particularly for $f > 3$). This work achieves the first significant progress on these problems: [$f$-Vertex Cut Labels:] Every $n$-vertex graph admits an $f$-vertex cut labeling scheme, where the labels have length of $\tilde{O}(n^{1-1/f})$ bits (when $f$ is polylogarithmic in $n$). This nearly matches the recent lower bound given by Long, Pettie and Saranurak (SODA 2025). [$f$-Vertex Cut Oracles:] For $f=O(\log n)$, every $n$-vertex graph $G$ admits $f$-vertex cut oracle with $\tilde{O}(n)$ space and $\tilde{O}(2^f)$ query time. We also show that our $f$-vertex cut oracles for every $1 \leq f \leq n$ are optimal up to $n^{o(1)}$ factors (conditioned on plausible fine-grained complexity conjectures). If $G$ is $f$-connected, i.e., when one is interested in \emph{minimum} vertex cut queries, the query time improves to $\tilde{O}(f^2)$, for any $1 \leq f \leq n$.

Merav Parter, Asaf Petruschka

We revisit the problem of fault-tolerant (FT) distance preservers, when failure events in the network admit a form of correlation modeled as color faults. FT distance preservers are sparse subgraphs that preserve distances between specified pairs of vertices, even after some edge or vertex failures occur. In the classical fault model, any set of at most $k$ edges or vertices might fail (where $k \geq 1$ is a given parameter). Despite extensive research, the classical model admits significant and tantalizing gaps, both in terms of sparsity bounds and of algorithmic efficiency. In this work, we study the problem in the recently introduced color fault-tolerant (CFT) model: the given graph $G=(V,E)$ has arbitrary colors on its edges/vertices where each color appears at most $k$ times, and is susceptible to color faults, where the failure of color $c$ causes all the $c$-colored elements to crash. Our main contribution is in the multi-source setting, where $G$ has a source-set $S \subseteq V$, and the CFT preserver should preserve $S \times V$ distances under any single color fault. We show the following results (where $n = |V|$, $m = |E|$): - There exists a CFT distance preserver $H$ of $G$ with $\tilde{O}(n^{2 - \frac{1}{k+1}} \cdot |S|^{\frac{1}{k+1}} )$ edges. - The above sparsity bound is worst-case optimal up to polylogarithmic terms. - There is a combinatorial randomized algorithm that produces a preserver $H$ whose size meets the above optimal sparsity bound, with running time of $\tilde{O}(m \cdot n^{1 - \frac{1}{k+1}} \cdot |S|^{\frac{1}{k+1}})$. - The above running time is conditionally optimal: a polynomial improvement would refute the combinatorial Boolean Matrix Multiplication (BMM) conjecture. Furthermore, the running time remains optimal even if we only require mild sparsification to $m^{1-ε}$ edges.

Koustav Bhanja, Merav Parter, Asaf Petruschka

We study Single-Source Mincut Sensitivity Oracles: compact data structures that, when queried with an edge e, report those affected vertices whose mincut value to source $s$ changes upon the insertion or failure of e. Insertion queries were treated by Baswana, Gupta, and Knollmann [Algorithmica '22], who showed an extremely compact oracle with only O(n) space. In this work, we consider edge failure queries, which are of even greater interest, but far more challenging. The current-best approaches give O(n^2) space: either using n-1 fixed-pair oracles of O(n) space each, based on the Picard-Queyranne representation [MPS '80], or using the O(n^2) space all-pairs oracle by Baswana and Pandey [SODA '22]. -Our key result is an optimal O(n) space single-source mincut sensitivity oracle for edge failure queries. It reports the set of affected vertices in O(n) time, thus matching the state-of-the-art bounds for the insertion case. -Additionally, we provide oracles with near-optimal query times at the cost of increasing the space to O(n^{1.5}). They can determine if any given vertex is affected by an insertion/failure of an edge in O(log n) time, or reports all affected vertices in amortized O(\log^3 n) time per vertex. Such oracles of subquadratic space were previously unknown, even for insertion. Our main technical contribution is in establishing novel and intricate connections between two seemingly distant objects, representing two different families of mincuts. The first is the DAG representation of farthest mincuts to the source, which was the central tool introduced by Baswana, Gupta, and Knollmann. The second is the Connectivity Carcass for Steiner mincuts of Dinitz and Vainshtein [STOC '94], which generalizes well-known cactus representations of global mincuts. Our work demonstrates the relatively unexplored potential of the carcass beyond its obvious Steiner mincuts scope.