Near-Optimal Vertex Fault-tolerant Labels �for Steiner Connectivity
Koustav Bhanja and Asaf Petruschka
Weizmann Institute of Science, Israel
ESA 2025
Funding: ERC grant of Merav Parter
2
Fault-tolerant (Global) Connectivity
3
Fault-tolerant (s,t)-Connectivity
�Steiner Connectivity: A Generalization
5
Fault-tolerant Steiner Connectivity
FT Global Connectivity
6
FT (s,t)-connectivity
Fault-tolerant Steiner Connectivity
Global Connectivity
Steiner Connectivity
A Generalization!
Main Problem
7
Design a Labeling Scheme
for Fault-tolerant Steiner Connectivity
What is a Labeling Scheme?
8
Existing Results for Extreme Scenarios
9
Global Connectivity
Steiner Connectivity
Our Results
[Bhanja and Petruschka, ESA 2025]
Does it solve the Steiner?
Generalizes global result
(different approach)
Fault-tolerant all-pairs
(s,t)-connectiviy
Overview of Our Results
11
Trivial Single Vertex Failure
12
13
Sub-optimal Solution
?
14
Let T be a Minimal Steiner Tree – leaves are terminals
True
15
Let T be a Minimal Steiner Tree – leaves are terminals
Fails
A Simple Labeling Scheme
,
What happens in Global Case?
A near optimal solution by Jiang, Parter, & Petruschka
“Good” Sparsifier seems impossible
For Steiner Connectivity
“One-high-deg”
“All-low-deg”
Labeling
Scheme
A ‘Dual’ Approach
“All-high-deg”
“One-low-deg”
Trivial: store for every subset
Nagamochi-Ibaraki Sparsifier
Recursively stored
Steiner Tree
Take Best-of-both
19
20
The Duan-Pettie Decomposition [SICOMP 2020]
“All-high-deg”
21
The Duan-Pettie Decomposition [SICOMP 2020]
22
Future Problems
Thank you.
Koustav Bhanja
Email: koustav.bhanja@weizmann.ac.il